Floyed算法
此算法由Robert W. Floyd（罗伯特·弗洛伊德）于1962年发表在“Communications of the ACM”上。同年Stephen Warshall（史蒂芬·沃舍尔）也独立发表了这个算法。Robert W．Floyd这个牛人是朵奇葩，他原本在芝加哥大学读的文学，但是因为当时美国经济不太景气，找工作比较困难，无奈之下到西屋电气公司当了一名计算机操作员，在IBM650机房值夜班，并由此开始了他的计算机生涯。
floyed是用动态规划解决完全最短路的算法，一次调用即可得到任意两个点间的最短路径，复杂度为O(n^3),适用于稠密图，顶点数一般在100以内适用，结构简单，易于编写。loyed算法还可解决传递闭包，判断图是否为连通图，在解题时候一般不会只考 floyed 而是利用floyed 得到的结果，进行下一步解题。
Floyed算法适用于求多源最短路的问题，即求任意两点之间最短路径。它和SPFA的相同点就是都可以求有负权值的边，但是不能有负回路。不同点就是SPFA算法处理的是单源最短路问题，而Floyd是求的是多源最短路问题。
#include<iostream> #include<algorithm> #include<cmath> #include<string> #include<cstring> #include<cstdlib> #include<map> #include<set> #include<cstdio> #include<queue> #include<list> #include<vector> #include<stack> #include<deque> using namespace std; //不可达的距离 const int maxpath=9999; const int n=107; //存节点之间距离 int Map[n][n]; //加边 void AddEdge(int from,int to,int weight) { Map[from][to]=weight; //有向图只写这一句 //Map[to][from]=weight;//无向图加上这一句 } //初始化距离，对角线上距离为0，其他的为不可达 void Init(int nodenum) { for(int i=1;i<=nodenum;i++) { for(int j=1;j<=nodenum;j++) { Map[i][j]=maxpath; } } for(int i=1;i<=nodenum;i++) { Map[i][i]=0; } } //Floyed算法，是否存在第三个节点k，使i节点和j节点之间的距离更短 void Floyed(int nodenum) { int i,j,k; for(int i=1; i<=nodenum; i++) for(int j=1; j<=nodenum; j++) for(int k=1; k<=nodenum; k++) { if(Map[i][j]>Map[i][k]+Map[k][j]) Map[i][j]=Map[i][k]+Map[k][j]; } } int main() { freopen("out.txt","r",stdin); //打开文件 int nodenum; //节点数 int edgenum; //边的条数 int from,to,weight; //一条有向边的开始节点、终点和权重 cin>>nodenum>>edgenum; Init(nodenum); for(int i=1;i<=edgenum;i++) { cin>>from>>to>>weight; AddEdge(from,to,weight); } Floyed(nodenum); //输出所有的最短路径 for(int i=1;i<=nodenum;i++) for(int j=1;j<=nodenum;j++) { cout<<Map[i][j]<<' '; } return 0; }
我将输入存到一个.txt文本里，第一行是节点数和边的数目，下面的8行是每条边的起点、终点和权值。
输入：4 8 1 2 2 1 3 4 1 4 6 2 3 3 3 1 7 3 4 1 4 1 5 4 3 12
最后的输出结果：0 2 4 5 10 0 3 4 6 8 0 1 5 7 9 0
