17、求任意两个节点之间最短距离——Floyd算法
Floyd算法:给出一个图(通常可以在任何图中使用,包括有向图、带负权边的图),求最短路径问题的一个O(n^3)算法。
优点:容易理解,可以算出任意两个节点之间最短距离的算法,程序容易写;
缺点:复杂度达到三次方,不适合计算大量数据;
它需要用邻接矩阵来储存边,这个算法通过考虑最佳子路径来得到最佳路径。注意单独一条边的路径也不一定是最佳路径。
Floyd-Warshall算法的基本思路是:
1.用d[i][j]记录每对顶点间的最短距离;
2.对每一个图中的顶点,以其作为基点扫描每一对d[i][j],检验是否通过该基点可以使得这对顶点间的距离变小。
//dist(i,j) 为从节点i到节点j的最短距离
Fori←1 to n do
For j←1 to n do
dist(i,j) = weight(i,j)
Fork←1 to n do // k为“媒介节点”
For i←1 to n do
For j←1 to n do
if (dist(i,k) + dist(k,j) < dist(i,j))then // 是否是更短的路径?
dist(i,j) = dist(i,k) + dist(k,j)
我们实际是很容易就可以写出这个算法的代码:
#defineN 100
voidFloyd(int dist[N][N],int n)
{
int i,j,k;
for(k=0;k for(i=0;i for(j=0;j if(dist[i][k]+dist[k][j] dist[i][j]=dist[i][k]+dist[k][j]; } 即使问题是求单源最短路径,还是推荐使用这个算法,如果时间和空间允许的话(只要有放的下邻接矩阵的空间,时间上就没问题)。 对上面的代码来说,我们还面临一个保存路径的问题,如何来做呢? /*多源最短路径floyd_warshall算法*/ #defineN 100 intmap[N][N]; voidFloyd(int dist[N][N],int path[N][N],int n) { int i,j,k; for(i=0;i for(j=0;j dist[i][j]=map[i][j], path[i][j]=0; for(k=0;k for(i=0;i for(j=0;j if(dist[i][k]+dist[k][j] { dist[i][j]=dist[i][k]+dist[k][j]; path[i][j]=k; } } voidoutput(int i,int j) { if(i==j) return; if(path[i][j]==0) cout<
① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件,版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源:我考网",违者本网将依法追究责任;
② 本网部分稿件来源于网络,任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益,应该及时向我考网书面反馈,并提供身份证明、权属证明及详细侵权情况证明,我考网在收到上述法律文件后,将会尽快移除被控侵权内容。