首页 > 代码库 > Floyd算法解决多源最短路径问题
Floyd算法解决多源最短路径问题
Floyd-Warshall算法是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权（但不可存在负权回路)的最短路径问题，同时也被用于计算有向图的传递闭包。
Floyd-Warshall算法的时间复杂度为O(N^3)，空间复杂度为O(N^2)。
Floyd-Warshall算法的原理是动态规划：
从i到j，要么是直接从i到j的，要么是从i出发经过中间节点到j的，假设中间节点有k种可能，那么只要求出这k种可能的最小值，即可得到最短路径。
d[ i ][ j ]=min{ d[ i ][ k ]+d[ k ][ j ],d[ i ][ k ] } (k from 0 to n)
#include<stdio.h>#include<stdlib.h>#include<string.h>#define max 100#define INF 999int graph[max][max];int vertex_num;int edge_num;int d[max][max];int p[max][max];void Floyd(){ int i,j,k; for(i=0;i<vertex_num;i++){ for(j=0;j<vertex_num;j++){ d[i][j]=graph[i][j]; p[i][j]=-1; } } for(k=0;k<vertex_num;k++){ for(i=0;i<vertex_num;i++){ for(j=0;j<vertex_num;j++){ if(d[i][j]>d[i][k]+d[k][j]){ d[i][j]=d[i][k]+d[k][j]; p[i][j]=k; } } } } }void find_path(int i,int j){ int k; k=p[i][j]; if(k==-1)return; find_path(i,k); printf("%d ",k); find_path(k,j);}void show_path(){ int i,j; printf("Output:\n"); for(i=0;i<vertex_num;i++){ for(j=0;j<vertex_num;j++){ if(d[i][j]==INF){ if(i!=j)printf("No path from %d to %d\n",i,j); }else{ printf("Path from %d to %d: ",i,j); printf("%d ",i); find_path(i,j); printf(" %d",j); printf(" distance:%-5d\n",d[i][j]); } } printf("\n"); }}int main(){ int i,j; FILE *fin = fopen ("dij.in", "r"); FILE *fout = fopen ("dij.out", "w"); char buf[10]; fgets(buf,10,fin); edge_num=atoi(buf); printf("edge_num:%d\n",edge_num); fgets(buf,10,fin); vertex_num=atoi(buf); printf("vertex_num:%d\n",vertex_num); for(i=0;i<edge_num;i++){ int start,end,weight;//start point,end point and the weight of edge fgets(buf,10,fin); sscanf(buf,"%d %d %d",&start,&end,&weight); printf("start:%d end:%d weight:%d\n",start,end,weight); graph[start][end]=weight;//init the graph matrix } Floyd(); show_path(); return 0;}
测资：
7
5
0 1 100
0 2 30
0 4 10
2 1 60
2 3 60
3 1 10
4 3 50
结果：
Output:
Path from 0 to 1: 0 4 3 1 distance:70
Path from 0 to 2: 0 2 distance:30
Path from 0 to 3: 0 4 3 distance:60
Path from 0 to 4: 0 4 distance:10
No path from 1 to 0
No path from 1 to 2
No path from 1 to 3
No path from 1 to 4
No path from 2 to 0
Path from 2 to 1: 2 1 distance:60
Path from 2 to 3: 2 3 distance:60
No path from 2 to 4
No path from 3 to 0
Path from 3 to 1: 3 1 distance:10
No path from 3 to 2
No path from 3 to 4
No path from 4 to 0
Path from 4 to 1: 4 3 1 distance:60
No path from 4 to 2
Path from 4 to 3: 4 3 distance:50
Floyd算法解决多源最短路径问题