手机网站建设经验/万网官网

基本思想： 

1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。

时间复杂度：O()

参考：弗洛伊德（Floyd）算法求图的最短路径  --- JeffCoding

代码：

#include<stdio.h>
#include<memory.h>
#define MAX 1000000int graph[100][100];   //存放边集及其权重 int path[100][100];  //存放最短路径 中除了起点终点的 第一个节点 int vertex[100];  //存放是否遍历过 int dis[100];void Creat_G(int vertnum){memset(graph,0,sizeof(graph));printf("输入图的邻接矩阵：\n");int i,j;for(i=1;i<=vertnum;i++){for(j=1;j<=vertnum;j++){scanf("%d",&graph[i][j]);if(graph[i][j]==0) {graph[i][j]=MAX;       //如果两点之间没有边这初始化graph为MAX}path[i][j]=j;   //初始化开始时的i，j两点间的最短路径的后继为 j }}printf("创建完成\n----------------------\n");
} void Floryd(int vertnum){int u,v,w,i;   //u 中间点  v 起始点  w 终点for(u=1;u<=vertnum;u++){for(v=1;v<=vertnum;v++){for(w=1;w<=vertnum;w++){if(v!=w && graph[v][w]>graph[v][u]+graph[u][w]){graph[v][w]=graph[v][u]+graph[u][w];path[v][w]=path[v][u];	// 更新最短路径中的除v,w外的第一个节点 }	}}}
}int main(){int num;printf("输入点的个数：\n");scanf("%d",&num);printf("-------------------------\n");Creat_G(num);Floryd(num);int i,j,u;for(i=1;i<=num;i++){for(j=1;j<=num;j++){printf("< %d , %d >  ",i,j);if(graph[i][j]==MAX)printf("$\t\n");else{printf("%d\t",graph[i][j]);u=path[i][j];printf("%d",i);for(;u!=j;u=path[u][j]){    //输出最短路径 printf("->%d",u); }printf("->%d\n",j);}}}return 0;
}