赞
踩
恰好今天看C语言算法和数学建模的方法都提到了这个算法
核心代码只有五行的算法
Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。通常可以在任何图中使用,包括有向图、带负权边的图。
Floyd-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边,这个算法通过考虑最佳子路径来得到最佳路径。
#include<stdio.h> int main() { int e[10][10],k,i,j,n,m,t1,t2,t3; int inf=99999999;//用inf存储我们认为的正无穷值 //读入n和m,n表示顶点个数,m表示边的条数 scanf("%d %d",&n,&m); //初始化 for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j) e[i][j]=0; else e[i][j]=inf; //读入边 for(i=1;i<=m;i++) { scanf("%d %d %d",&t1,&t2,&t3); e[t1][t2]=t3; } //floyd-warshali算法核心语句 for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(e[i][j]>e[i][k]+e[k][j]) e[i][j]=e[i][k]+e[k][j]; //输出最终的结果 for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { printf("%10d",e[i][j]); } printf("\n"); } return 0; }
顺便附上MATLAB的代码吧
tulun2.m a= [ 0,50,inf,40,25,10; 50,0,15,20,inf,25; inf,15,0,10,20,inf; 40,20,10,0,10,25; 25,inf,20,10,0,55; 10,25,inf,25,55,0]; [D, path]=floyd(a) floyd.m function [D,path,min1,path1]=floyd(a,start,terminal) D=a;n=size(D,1);path=zeros(n,n); for i=1:n for j=1:n if D(i,j)~=inf path(i,j)=j; end, end, end for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k); end, end, end, end if nargin==3 min1=D(start,terminal); m(1)=start; i=1; path1=[ ]; while path(m(i),terminal)~=terminal k=i+1; m(k)=path(m(i),terminal); i=i+1; end m(i+1)=terminal; path1=m; end
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。