下面是我按照严蔚敏老师的C语言版数据结构P189编写的弗洛伊德算法，在VC++6.0下运行通过
#include "stdio.h" #include "stdlib.h" #define MAX 20 #define INFINITY 9999 typedef bool PathMatrix[MAX+1][MAX+1][MAX+1]; typedef int DistanceMatrix[MAX+1][MAX+1]; typedef struct { int vexnum,arcnum; char vexs[MAX+1]; int arcs[MAX+1][MAX+1]; }MGraph; void CreateDN(MGraph &G) { int i,j,k,v1,v2,w; printf("请输入顶点数和边数:"); scanf("%d %d",&G.vexnum,&G.arcnum); for(i=0;i<G.vexnum;i++) { getchar(); printf("请输入第%d个结点：",i); scanf("%c",&G.vexs[i]); } for(i=0;i<G.vexnum;i++) for(j=0;j<G.vexnum;j++) G.arcs[i][j]=INFINITY; for(k=0;k<G.arcnum;k++) { printf("请输入边----源点，终点，权值："); scanf("%d %d %d",&v1,&v2,&w); G.arcs[v1][v2]=w; } } void ShortestPath_FLOYD(MGraph G,PathMatrix &P,DistanceMatrix &D) { int v,w,u,i; for(v=0;v<G.vexnum;++v) for(w=0;w<G.vexnum;++w) { D[v][w]=G.arcs[v][w]; for(u=0;u<G.vexnum;++u) P[v][w][u]=false; if (D[v][w]<INFINITY) { P[v][w][v]=true; P[v][w][w]=true; } } for(u=0;u<G.vexnum;++u) for(v=0;v<G.vexnum;++v) for(w=0;w<G.vexnum;++w) if (D[v][u]+D[u][w]<D[v][w]) { D[v][w]=D[v][u]+D[u][w]; for(i=0;i<G.vexnum;++i) P[v][w][i]=P[v][u][i]||P[u][w][i]; } } void main() { MGraph G; int i,j,k; CreateDN(G); PathMatrix p; DistanceMatrix D; ShortestPath_FLOYD(G,p,D); for(i=0;i<G.vexnum;i++) for(j=0;j<G.vexnum;j++) { printf("%d到顶点%d的最短路径为:/n",i,j); for(k=0;k<G.vexnum;k++) printf("%d ",p[i][j][k]); printf("代价为:%d/n",D[i][j]); printf("/n"); } }
输入输出例如下例：
请输入顶点数和边数:6 8请输入第0个结点：a请输入第1个结点：b请输入第2个结点：c请输入第3个结点：d请输入第4个结点：e请输入第5个结点：f请输入边----源点，终点，权值：0 2 10请输入边----源点，终点，权值：0 5 100请输入边----源点，终点，权值：0 4 30请输入边----源点，终点，权值：1 2 5请输入边----源点，终点，权值：2 3 50请输入边----源点，终点，权值：4 5 60请输入边----源点，终点，权值：3 5 10请输入边----源点，终点，权值：4 3 200到顶点0的最短路径为:0 0 0 0 0 0 代价为:9999
0到顶点1的最短路径为:0 0 0 0 0 0 代价为:9999
0到顶点2的最短路径为:1 0 1 0 0 0 代价为:10
0到顶点3的最短路径为:1 0 0 1 1 0 代价为:50
0到顶点4的最短路径为:1 0 0 0 1 0 代价为:30
0到顶点5的最短路径为:1 0 0 1 1 1 代价为:60
1到顶点0的最短路径为:0 0 0 0 0 0 代价为:9999
1到顶点1的最短路径为:0 0 0 0 0 0 代价为:9999
1到顶点2的最短路径为:0 1 1 0 0 0 代价为:5
1到顶点3的最短路径为:0 1 1 1 0 0 代价为:55
1到顶点4的最短路径为:0 0 0 0 0 0 代价为:9999
1到顶点5的最短路径为:0 1 1 1 0 1 代价为:65
2到顶点0的最短路径为:0 0 0 0 0 0 代价为:9999
2到顶点1的最短路径为:0 0 0 0 0 0 代价为:9999
2到顶点2的最短路径为:0 0 0 0 0 0 代价为:9999
2到顶点3的最短路径为:0 0 1 1 0 0 代价为:50
2到顶点4的最短路径为:0 0 0 0 0 0 代价为:9999
2到顶点5的最短路径为:0 0 1 1 0 1 代价为:60
3到顶点0的最短路径为:0 0 0 0 0 0 代价为:9999
3到顶点1的最短路径为:0 0 0 0 0 0 代价为:9999
3到顶点2的最短路径为:0 0 0 0 0 0 代价为:9999
3到顶点3的最短路径为:0 0 0 0 0 0 代价为:9999
3到顶点4的最短路径为:0 0 0 0 0 0 代价为:9999
3到顶点5的最短路径为:0 0 0 1 0 1 代价为:10
4到顶点0的最短路径为:0 0 0 0 0 0 代价为:9999
4到顶点1的最短路径为:0 0 0 0 0 0 代价为:9999
4到顶点2的最短路径为:0 0 0 0 0 0 代价为:9999
4到顶点3的最短路径为:0 0 0 1 1 0 代价为:20
4到顶点4的最短路径为:0 0 0 0 0 0 代价为:9999
4到顶点5的最短路径为:0 0 0 1 1 1 代价为:30
5到顶点0的最短路径为:0 0 0 0 0 0 代价为:9999
5到顶点1的最短路径为:0 0 0 0 0 0 代价为:9999
5到顶点2的最短路径为:0 0 0 0 0 0 代价为:9999
5到顶点3的最短路径为:0 0 0 0 0 0 代价为:9999
5到顶点4的最短路径为:0 0 0 0 0 0 代价为:9999
5到顶点5的最短路径为:0 0 0 0 0 0 代价为:9999
Press any key to continue
如有不足的地方请大家多多指教！
