【前言】：前面的Dijkstra算法用来解决单源最短路径的问题，即：从指定点到图上其他各点的最短路径。那么，如果我们要求图中任意两个结点之间的最短路径，如何用算法来实现呢？如果用Dijkstra来实现，就需要每次改变源点，再使用多个dis数组来记录，这样，问题就会变得很复杂。那么，有没有一种简单的算法来求图中任意两个结点之间的最短路径呢？当然有！那就是 Flody算法。
利用类似三角形定理：三角形的任意两边之和大于或等于第三边；
【算法思想】：求A到B的最短路径，Flody算法的核心思想就是找到一个中转站C，使得从A到C再到B的距离比从A直接到B的距离短； 核心算法就是在N个结点中找到每次合适的一个中转站k：
for (k = 0; k < n; k++)//在n个结点中依次找中转站； { for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { if (mp[i][j] > mp[i][k] + mp[k][j])//如果直接从i到j的距离大于从i到k再到j的距离，即找到一个合适的中转站，就更新地图； { mp[i][j] = mp[i][k] + mp[k][j]; } } } }例如：
有向图：
完整代码实现如下：
#include<iostream> using namespace std; #define N 1000 int mp[N][N];//用邻接矩阵来存图 #define INF 0x3f3f3f3f void inin(int n)//初始化，结点自己和自己之间的距离为0，其他的为无穷大； { int i, j; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { if (i == j) mp[i][j] = 0; else { mp[i][j] = INF; } } } } void flody(int n)//核心算法 { int k, i, j; for (k = 0; k < n; k++)//在n个结点中依次找中转站； { for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { if (mp[i][j] > mp[i][k] + mp[k][j])//如果直接从i到j的距离大于从i到k再到j的距离，即找到一个合适的中转站，就更新地图； { mp[i][j] = mp[i][k] + mp[k][j]; } } } } } int main() { int n, m; int i, j,k; cin >> n >> m;//n个结点m条边 inin(n); for (i = 0; i < m; i++)//注意：这里是有向图；如果是无向图，则加上：mp[b][a]=c; { int a, b, c; cin >> a >> b >> c; mp[a][b] = c; } flody(n); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { cout << i << "---->" << j << ":";//输出从i到j的最短路径； if (mp[i][j] == INF) cout << "oo"<<endl;//oo表示无穷大，即不联通； else cout << mp[i][j] << endl; } } return 0; }输入：
4 6 0 1 5 0 2 2 0 3 7 1 2 6 1 3 1 2 3 2
输出：
起点 终点 最短路径 0 ----> 0: 0 0 ----> 1: 5 0 ----> 2: 2 0 ----> 3: 4 1 ----> 0: oo 1 ----> 1: 0 1 ----> 2: 6 1 ----> 3: 1 2 ----> 0: oo 2 ----> 1: oo 2 ----> 2: 0 2 ----> 3: 2 3 ----> 0: oo 3 ----> 1: oo 3 ----> 2: oo 3 ----> 3: 0
