本文目录一览：
- 1、c语言最短路径问题。
- 2、C语言畅通工程
- 3、最短路径算法 C语言
- 4、一道C语言棋盘最优路径的题目，求教
- 5、怎么用c语言实现单源最短路径问题？要求是用Dijkstra算法，最好写出所有的代码 ，包括结构定义等等，对一
c语言最短路径问题。
#include stdio.h
#define N 7 /* 顶点数目 */
#define I 999 /* 表示无穷大 */
int graph[N][N] = { /* 图的邻接矩阵 */
{I, 4, 5, 8, I, I, I},
{I, I, I, 6, 6, I, I},
{I, I, I, 5, I, 7, I},
{I, I, I, I, 8, 9, 9},
{I, I, I, I, I, I, 5},
{I, I, I, I, I, I, 4},
{I, I, I, I, I, I, I}
};
int List[N]; /* 存放拓扑序列 */
int TopologicalOrder(); /* 拓扑排序函数 */
void main() /* 主 函 数 */
{
int i, j, k, l;
int ee[N], el[N]; /* 最长最短距离 */
int path_e[N][N], path_l[N][N], n_e[N], n_l[N]; /* 记录路径数据 */
/* 初始化数据 */
for (i = 0; i N; i++) {
n_e[i] = 0; /* 到 i 的最短路线的结点数 */
n_l[i] = 0; /* 到 i 的最长路线的结点数 */
ee[i] = I;
el[i] = 0;
}
ee[0] = el[0] = 0; /* 初始化头结点 */
path_e[0][0] = 0;
path_l[0][0] = 0;
n_e[0] = 1;
n_l[0] = 1;
/* 拓扑排序 */
if (!TopologicalOrder())
return;
/* 对于拓扑序列,运用动态规划步步算出最长路线与最短路线 */
for (i = 0; i N; i++) {
/* 提取拓扑序列的元素 */
k = List[i];
/* 更新它所指向顶点的所有数据 */
for (j = 0; j N; j++) {
/* 寻找指向的顶点 */
if (graph[k][j] != I) {
/* 如果新路径更短 */
if (graph[k][j] + ee[k] ee[j]) {
/* 更新最短路径长度 */
ee[j] = graph[k][j] + ee[k];
/* 更新最短路线 */
for (l = 0; l n_e[k]; l++) {
path_e[j][l] = path_e[k][l];
}
path_e[j][l] = j;
n_e[j] = l + 1;
}
/* 如果新路径更长 */
if (graph[k][j] + el[k] el[j]) {
/* 更新最长路径长度 */
el[j] = graph[k][j] + el[k];
/* 更新最长路线 */
for (l = 0; l n_l[k]; l++) {
path_l[j][l] = path_l[k][l];
}
path_l[j][l] = j;
n_l[j] = l + 1;
}
}
}
}
/* 输出结果到屏幕 */
for (i = 0; i N; i++) {
printf("shortest(%d): %2d Path: ", i + 1, ee[i]);
for (j = 0; j n_e[i]; j++) {
printf("%d ", path_e[i][j] + 1);
}
printf("\n");
printf("longest (%d): %2d Path: ", i + 1, el[i]);
for (j = 0; j n_l[i]; j++) {
printf("%d ", path_l[i][j] + 1);
}
printf("\n");
}
}
int TopologicalOrder()
{
int i, j, top, count;
int indegree[N], Stack[N];
top = 0; /* 栈顶标志 */
for (i = 0; i N; i++) {
indegree[i] = 0; /* 初始化入度 */
for (j = 0; j N; j++) {
if (graph[j][i] != I) { /* 如连通 */
indegree[i]++; /* 入度自增1 */
}
}
if (!indegree[i]){ /* 如入度为零 */
Stack[top++] = i; /* 入栈 */
}
}
count = 0; /* 输出顶点数 */
while (top != 0) {
i = Stack[--top];
List[count++] = i;
for (j = 0; j N; j++) {
if (graph[i][j] != I) { /* 如连通 */
if (!(--indegree[j])) { /* 而且入度为零 */
Stack[top++] = j; /* 入栈 */
}
}
}/* for */
}/* while */
return (count N) ? 0 : 1;
}
C语言畅通工程
//是最小生成树算法
#includestdio.h
#includestring.h
const int INF=1000000000;
const int MAX=105;
int map[MAX][MAX],cost[MAX];
bool used[MAX];
int MST(int n)
{
int i,j,k,min_;
int ret=0;
memset(used,false,sizeof(used));
for(i=0;in;i++)
cost[i]=map[0][i];
cost[0]=0;
for(i=0;in;i++)
{
k=-1;
min_=INF;
for(j=0;jn;j++)
{
if(!used[j]cost[j]min_)
{
k=j;
min_=cost[j];
}
}
used[k]=true;
ret+=cost[k];
for(j=0;jn;j++)
{
if(!used[j]map[k][j]cost[j])
cost[j]=map[k][j];
}
}
return ret;
}
int main()
{
int n,i,j;
int a,b,c;
while(scanf("%d",n)!=EOFn)
{
for(i=0;in;i++)
for(j=0;jn;j++)
map[i][j]=INF;
for(i=0;i(n-1)*n/2;i++)
{
scanf("%d%d%d",a,b,c);
a--;
b--;
if(map[a][b]c)map[a][b]=map[b][a]=c;
}
printf("%d\n",MST(n));
}
return 0;
}
最短路径算法 C语言
#include stdio.h
#define MAXNODE 108
int path[MAXNODE + 1][MAXNODE + 1] = {0};
int main(void)
{
FILE *fpr, *fpw;
int va, vb, i, j, k;
fpr = fopen("in.txt", "r"); /* 读取的文件名称in.txt */
fpw = fopen("out.txt", "w"); /* path的数据在out.txt中展现 */
while (fscanf(fpr, "%d%d", va, vb) != EOF)
path[va][vb] = path[vb][va] = 1;
for (k = 1; k = MAXNODE; ++k) {
for (i = 1; i = MAXNODE; ++i) {
for (j = 1; j = MAXNODE; ++j) {
if (!path[i][k] || !path[k][j])
continue;
if (!path[i][j])
path[i][j] = path[i][k] + path[k][j];
else if (path[i][j] path[i][k] + path[k][j])
path[i][j] = path[i][k] + path[k][j];
}
}
}
for (i = 1; i = MAXNODE; ++i) {
for (j = 1; j = MAXNODE; ++j) {
if (i == j)
fprintf(fpw, "%-10d", 0);
else if (path[i][j])
fprintf(fpw, "%-10d", path[i][j]);
else
fprintf(fpw, "%-10d", -1);
}
fprintf(fpw, "\n");
}
return 0;
}
注意：floyd算法中k为最外层，这是动态规划的思想，不能改变i,j,k的顺序！！！
这是之前的答案的错误之处。
-1表示不通。
具体程序分析，我可以加你QQ，愿意的话，你把QQ写给我。
一道C语言棋盘最优路径的题目，求教
这题还是有点意思的。
正如diordna所说，因为涉及到全局最优，
大小又是1000x1000，感觉广搜有点困难，所以打算试试DP。。
思路如下，不知道对不对。。
Part.1
设map[i][j]保存棋盘格子的价值 (i = 0..n-1, j = 0..m-1)
设f[i][j][k]记录棋盘(i, j)位置的最大价值和 (i = 0..n-1, j = 0..m-1, k = 0,1,2)
k表示这个位置是怎么来的：
k = 0: 左→右
k = 1: 上→下
k = 2: 下→上
首先初始化 f[i][j][k] = -inf
然后根据题意有：f[0][0][k] = map[0][0], k = 0,1,2
Part.2
又因为不能向左走，实际上就是说第j = 0列的格子只能向下走
所以可以先把f[i][0][1]算出来
f[i][0][1] = max(k=0,1){f[i-1][0][k]} + map[0][j] = f[i-1][0][1] + map[i][0], i = 1..n-1
Part.3
然后考虑任意一个非第0列的格子(i, j), i = 0..n-1, j = 1..m-1
便于思考特殊化一下，假设考虑第j = 1列（当然其它列也一样），
任意一个格子有3种到达方式，分别对应k = 0, 1, 2
但此时我们只知道每个格子的左边格子里的f值
那么我们先计算k=0时刻各格子的f值 (左→右)
f[i][j][0] = max(k=0,1,2){f[i][j-1][k]} + map[i][j], i = 0..n-1, j = 1
Part.4
这样一来各个格子从左边来到后的总价值f就得到了
接下来处理从上到下和从下到上的情况
由于从某个格子开始一旦选择从上到下或从下到上走后就无法回头了
不妨从上到下开始：
f[i][j][1] = max(k=0,1){f[i-1][j][k]} + map[i][j], i = 1..n-1, j = 1
然后从下到上：
f[i][j][2] = max(k=0,2){f[i+1][j][k]} + map[i][j], i = n-2..0, j = 1
Part.5
这样一来每个格子对应的3种走法的价值最大值就能得到了
如此回到Part.3循环列j = 1..m-1
最后只要取max(k=0,1){f[n-1][m-1][k]} 即可得到最优路径价值和
试着写了一下，不知道能不能过。。
注意由于开了1000x1000的long数组，所以VC调试的时候注意把堆栈开大一点
#include iostream
using namespace std;
#define MAXN 1000
#define INF 0x7fffffff
long map[MAXN][MAXN];
long f[MAXN][MAXN][3];
long getmax(long a, long b){ return (a b) ? a : b;}
void init()
{
for(int i = 0; i MAXN; i++)
{
for(int j = 0; j MAXN; j++)
{
map[i][j] = -INF;
f[i][j][0] = -INF;
f[i][j][1] = -INF;
f[i][j][2] = -INF;
}
}
}
int main()
{
// Part.1
int n, m;
cin n m;
init();
for(int i=0; in; i++)
{
for(int j=0; jm; j++)
{
cin map[i][j];
}
}
f[0][0][0] = f[0][0][1] = f[0][0][2] = map[0][0];
// Part.2
for(int i=1; in; i++)
{
f[i][0][1] = f[i-1][0][1] + map[i][0];
}
for(int j=1; jm; j++)
{
// Part.3
for(int i=0; in; i++)
{
long max = getmax(getmax(f[i][j-1][0], f[i][j-1][1]), f[i][j-1][2]);
if(max == -INF) continue;
f[i][j][0] = max + map[i][j];
}
// Part.4
for(int i=1; in; i++)
{
long max = getmax(f[i-1][j][0], f[i-1][j][1]);
if(max == -INF) continue;
f[i][j][1] = max + map[i][j];
}
for(int i=n-2; i=0; i--)
{
long max = getmax(f[i+1][j][0], f[i+1][j][2]);
if(max == -INF) continue;
f[i][j][2] = max + map[i][j];
}
}
cout getmax(f[n-1][m-1][0], f[n-1][m-1][1]) endl;
return 0;
}
怎么用c语言实现单源最短路径问题？要求是用Dijkstra算法，最好写出所有的代码 ，包括结构定义等等，对一
C语言代码：//清华大学出版社光盘的代码
void ShortestPath_DIJ(MGraph G,int v0,PathMatrix P,ShortPathTable D)
{ // 算法7.15
// 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]
// 及其带权长度D[v]。
// 若P[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点。
// final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径。
int i=0,j, v,w,min;
bool final[MAX_VERTEX_NUM];
for (v=0; vG.vexnum; ++v) {
final[v] = FALSE;
D[v] = G.arcs[v0][v].adj;
for (w=0; wG.vexnum; ++w) P[v][w] = FALSE; // 设空路径
if (D[v] INFINITY) { P[v][v0] = TRUE; P[v][v] = TRUE; }
}
D[v0] = 0; final[v0] = TRUE; // 初始化，v0顶点属于S集
//--- 开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集 ---
for (i=1; iG.vexnum; ++i) { // 其余G.vexnum-1个顶点
min = INFINITY; // 当前所知离v0顶点的最近距离
for (w=0; wG.vexnum; ++w)
if (!final[w]) // w顶点在V-S中
if (D[w]min) { v = w; min = D[w]; } // w顶点离v0顶点更近
final[v] = TRUE; // 离v0顶点最近的v加入S集
for (w=0; wG.vexnum; ++w) // 更新当前最短路径及距离
if (!final[w] (min+G.arcs[v][w].adjD[w])) {
// 修改D[w]和P[w], w∈V-S
D[w] = min + G.arcs[v][w].adj;
for(j=0;jG.vexnum;j++) P[w][j] = P[v][j]; //第v行赋值于第w行
P[w][w] = TRUE; // P[w] = P[v]+[w]
}//if
}//for
} // ShortestPath_DIJ
