C++实现Floyd算法，求解所有点间的最短距离_很多点两两比较距离最短算法 c++

1，原理

Floyd算法用来求解所有顶点间的最短距离，可以应用于有向图和无向图。基本思想是，先用矩阵存储各个点间的直达路径，然后将各个顶点依次加入，每加入一个顶点，就以该点为中间点，计算各个点间的路径在通过该中间点的情况下是否比原来的短，若短，则更新路径长度。将所有顶点都加入后，所得矩阵的每个数据就是对应两点间的最短路径。

2，举例

如图，以无向图为例
1，用初始矩阵dist存储各个点的直达路径距离，dist[i][j]表示从vi到vj的距离，各个点到自身距离为0，若两点无法直达，则距离为Max。（这里因为是无向图，所以 dist[i][j] = dist[j][i] ）

2，将v0点加入，由于dist[2][0] + dist[0][3] = 5 < dist[2][3] = 6, 所以 dist[2][3] = dist[3][2] = 5; 同理，dist[2][0] + dist[0][1] = 3 < dist[2][1] = Max, 所以 dist[2][1] = dist[1][2] = 3;

3,继续加入顶点更新矩阵，待全部加入后，所得矩阵中 dist[i][j] 的值即为从vi到vj得最短距离。

3，代码实现

#include<iostream>
using namespace std;
#define Max 9999

int n, m;
int dist[Max][Max]
1
2
3
4
5