Floyd算法分析和实现
其实我觉得这个算法还是很简单的，但是看网上的资料感觉很高深，说的我稀里糊涂的。难道是我想错啦？希望大神帮我指正（真心没自信）。。谢谢。
/*Floyd算法：可以解决任何两点间的最短距离问题。而dijkstra算法是解决源节点和目的节点两个之间的最短距离问题。Floyd算法思想: 如果两点的最短距离不是两点的带权路径的权值，而是通过中间的某个节点或多个节点才有了这个最短路径。所以我们对于任何两个节点的最短路径问题可以这么考虑：其他节点和这个最短路径只有两种关系:在这个最短路径序列中和不在这个最短路径序列中。假如有V0--Vn这么多个节点，那么任意两个节点Vi和Vj，分别考虑当插入V0--Vn后Vi和Vj的距离。当插入所有的节点后，任何两个节点的最短路径就求出来了，复杂度为O(n^3);*/#include<iostream>using namespace std;#define MAX 1024int D[MAX][MAX];//记录任何两个节点的距离int A=0;void findThePath(int nodes){int i,j,k;for(i=1;i<nodes;i++){for(j=0;j<nodes;j++){if(j!=A){for(k=j+1;k<nodes;k++){if((j!=k)&&D[j][k]>D[j][i]+D[i][k]){D[j][k]=D[j][i]+D[i][k];D[k][j]=D[j][k];}}}}A++;}}void main(){int nodes,edges;int firstnode,secondnode,dis;int i,j;while(1){cin>>nodes>>edges;for(i=0;i<nodes;i++)for(j=0;j<nodes;j++){if(i==j)D[i][j]=0;elseD[i][j]=MAX;}for(i=0;i<edges;i++){cin>>firstnode>>secondnode>>dis;D[firstnode][secondnode]=dis;D[secondnode][firstnode]=dis;}findThePath(nodes);cout<<"0和3的最小路径:"<<D[0][3]<<endl;cout<<"1和2的最小路径:"<<D[1][2]<<endl;cout<<"2和3的最小路径:"<<D[2][3]<<endl;cout<<"1和3的最小路径:"<<D[1][3]<<endl;cout<<"0和1的最小路径:"<<D[0][1]<<endl;}}