这个算法形式很简单。
如果去求每两个顶点之间的最短路径，我们用其中一个顶点作为源点，去看看通过其他一个点到其他点最短距离是多少，也就是重复执行Dijkstra算法n次，就可以求得每一对顶点的最短路径。时间复杂度高！！！就是形式简单。本质是动态规划，设D[I,J]为i到J最短路径，则其动态规划的状态转移方程为：
D[I,J]=min(D[I,K]+D[K,J],D[I,J]) (1<=k<=n)
---------------------------------------------------------------------------------------------------------------------------------------
代码：
#include<iostream> #define maxn 100 using namespace std; int n,s,t;//点数，要求的两个点之间最短距离的起点，终点 int a[maxn+1][maxn+1]; void init() { int m,i,u,v; cout<<"点数和边数"<<endl; cin>>n>>m; for(u=1;u<=n;u++) for(v=1;v<=n;v++) a[u][v]=-1; cout<<"边起点 边终点 边权值"<<endl; for(i=1;i<=m;i++){ cin>>u>>v; cin>>a[u][v]; } cout<<"你需要计算那两个点之间的最短距离？"<<endl; cin>>s>>t; } void floyd(){ int i,j,k; // for(k=1;k<=n;k++)//循环N次 for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(a[i][k]!=-1 && a[k][j]!=-1)//要可达 if(a[i][k]+a[k][j]<a[i][j])//找到最短的，记住这个循环先是K,否则就会在很早之前就误以为i,j是最短的。照成错误 a[i][j]=a[i][k]+a[k][j];//更新 } /*测试数据 3 5 1 2 4 2 1 6 1 3 11 3 1 3 2 3 2 */ int main() {//测试 init(); floyd(); cout<<"结果为："<<endl; cout<<a[s][t]<<endl; return 0; }
