图相关文章：
1. 图的建立 - 邻接矩阵与邻接表
2. 图的遍历 - DFS与BFS
3. 顶点度的计算
4. 最小生成树 - Prim与Kruskal
5. 单源最短路径 - Dijkstra与Bellman-Ford
6. 多源最短路径 - Floyd
7. 拓扑排序AOV网
Floyd算法是求解多源最短路径问题的典型算法，可以知道图中任意两点之间的最短路径。该算法对于有向图、无向图都适用，同时允许图中带有负权边，但是不允许有负权环。
Floyd算法采用动态规划的思想，分为多个阶段来解决问题。
若图 G G G有 n n n个顶点 ( V 0 ∼ V n − 1 ) (V_0 \sim V_{n-1}) (V0∼Vn−1)，则将求图中每一对顶点之间的最短路径分 n n n个阶段∶
Floyd求解过程：
首先进行初始化，在没有其它顶点中转的情况下，求得各顶点间的最短路径；
在各顶点间增加 V 0 V_0 V0作为中转结点，求得各顶点间新的最短路径；
再增加 V 1 V_1 V1作为中转结点，求得各顶点间新的最短路径；
……
最后增加 V n − 1 V_{n-1} Vn−1作为中转结点，求得各顶点间最终的最短路径。
Floyd只能使用邻接矩阵来实现。
为了方便理解，我们来手动模拟一下实现过程。以有向图演示，无向图同理。
我们使用两个大小为 n × n n \times n n×n的二维数组分别记录最短路径 d i s dis dis与中转顶点 p a t h path path。其中，最短路径矩阵可以告诉我们任意两顶点间的最短距离；而中转顶点矩阵可以告诉我们路径。
（1）初始化
初始化的最短路径矩阵其实就是邻接矩阵，中转顶点矩阵全部标记为
−
1
-1
−1，代表未经过中转。
① 加入 V 0 V_0 V0中转
可以看到， V 0 V_0 V0顶点的入度为0，所以任何顶点都不能到达 V 0 V_0 V0，最短路径与中转顶点矩阵不变。
没有别的顶点可以通过 V 1 V_1 V1中转或使得 d i s dis dis减少，进行下一次中转。
② 加入 V 1 V_1 V1中转
可以看到，当我们添加到 V 1 V_1 V1作为中转时，
原先 V 2 → V 3 = ∞ V_2 \rightarrow V_3 = \infty V2→V3=∞，现在 V 2 → V 1 → V 3 = 2 V_2 \rightarrow V_1 \rightarrow V_3= 2 V2→V1→V3=2，更新 d i s [ V 2 ] [ V 3 ] = 2 dis[V_2][V_3]=2 dis[V2][V3]=2， p a t h [ V 2 ] [ V 3 ] = 1 path[V_2][V_3]=1 path[V2][V3]=1
原先 V 2 → V 4 = 7 V_2 \rightarrow V_4 = 7 V2→V4=7，现在 V 2 → V 1 → V 4 = 6 V_2 \rightarrow V_1 \rightarrow V_4= 6 V2→V1→V4=6，更新 d i s [ V 2 ] [ V 4 ] = 6 dis[V_2][V_4]=6 dis[V2][V4]=6， p a t h [ V 2 ] [ V 4 ] = 1 path[V_2][V_4]=1 path[V2][V4]=1
没有别的顶点可以通过 V 1 V_1 V1中转或使得 d i s dis dis减少，进行下一次中转。
③ 加入 V 2 V_2 V2中转
可以看到，当我们添加到 V 2 V_2 V2作为中转时，
原先 d i s [ V 0 ] [ V 1 ] = ∞ dis[V_0][V_1] = \infty dis[V0][V1]=∞，现在 d i s [ V 0 ] [ V 2 ] + d i s [ V 2 ] [ V 1 ] = 2 dis[V_0][V_2] + dis[V_2][V_1]= 2 dis[V0][V2]+dis[V2][V1]=2，更新 d i s [ V 0 ] [ V 1 ] = 2 dis[V_0][V_1]=2 dis[V0][V1]=2， p a t h [ V 0 ] [ V 1 ] = 2 path[V_0][V_1]=2 path[V0][V1]=2
原先 d i s [ V 0 ] [ V 3 ] = ∞ dis[V_0][V_3] = \infty dis[V0][V3]=∞，现在 d i s [ V 0 ] [ V 2 ] + d i s [ V 2 ] [ V 3 ] = 3 dis[V_0][V_2] + dis[V_2][V_3]= 3 dis[V0][V2]+dis[V2][V3]=3，更新 d i s [ V 0 ] [ V 3 ] = 3 dis[V_0][V_3]=3 dis[V0][V3]=3， p a t h [ V 0 ] [ V 3 ] = 2 path[V_0][V_3]=2 path[V0][V3]=2
原先 d i s [ V 0 ] [ V 4 ] = 10 dis[V_0][V_4] = 10 dis[V0][V4]=10，现在 d i s [ V 0 ] [ V 2 ] + d i s [ V 2 ] [ V 4 ] = 7 dis[V_0][V_2] + dis[V_2][V_4]= 7 dis[V0][V2]+dis[V2][V4]=7，更新 d i s [ V 0 ] [ V 4 ] = 7 dis[V_0][V_4]=7 dis[V0][V4]=7， p a t h [ V 0 ] [ V 4 ] = 2 path[V_0][V_4]=2 path[V0][V4]=2
没有别的顶点可以通过 V 2 V_2 V2中转或使得 d i s dis dis减少，进行下一次中转。
④ 加入 V 3 V_3 V3中转
可以看到，当我们添加到 V 3 V_3 V3作为中转时，
原先 d i s [ V 0 ] [ V 4 ] = 7 dis[V_0][V_4] = 7 dis[V0][V4]=7，现在 d i s [ V 0 ] [ V 3 ] + d i s [ V 3 ] [ V 4 ] = 4 dis[V_0][V_3] + dis[V_3][V_4]= 4 dis[V0][V3]+dis[V3][V4]=4，更新 d i s [ V 0 ] [ V 4 ] = 4 dis[V_0][V_4]= 4 dis[V0][V4]=4， p a t h [ V 0 ] [ V 4 ] = 3 path[V_0][V_4]=3 path[V0][V4]=3
原先 d i s [ V 1 ] [ V 4 ] = 5 dis[V_1][V_4] = 5 dis[V1][V4]=5，现在 d i s [ V 1 ] [ V 3 ] + d i s [ V 3 ] [ V 4 ] = 2 dis[V_1][V_3] + dis[V_3][V_4]= 2 dis[V1][V3]+dis[V3][V4]=2，更新 d i s [ V 1 ] [ V 4 ] = 2 dis[V_1][V_4]=2 dis[V1][V4]=2， p a t h [ V 1 ] [ V 4 ] = 3 path[V_1][V_4]=3 path[V1][V4]=3
原先 d i s [ V 2 ] [ V 4 ] = 6 dis[V_2][V_4] = 6 dis[V2][V4]=6，现在 d i s [ V 2 ] [ V 3 ] + d i s [ V 3 ] [ V 4 ] = 3 dis[V_2][V_3] + dis[V_3][V_4]= 3 dis[V2][V3]+dis[V3][V4]=3，更新 d i s [ V 2 ] [ V 4 ] = 3 dis[V_2][V_4]=3 dis[V2][V4]=3， p a t h [ V 1 ] [ V 4 ] = 3 path[V_1][V_4]=3 path[V1][V4]=3
没有别的顶点可以通过 V 3 V_3 V3中转或使得 d i s dis dis减少，进行下一次中转。
⑤ 加入 V 4 V_4 V4中转
可以看到，当我们添加到 V 4 V_4 V4作为中转时，由于 V 4 V_4 V4的出度为0，故不会进行更新，且已经将所有顶点中转完成，得到的便是最终结果。
d i s [ i ] [ j ] dis[i][j] dis[i][j]存储的便是 V i ∼ V j V_i \sim V_j Vi∼Vj的最短路径长度。
而想要输出 V i ∼ V j V_i \sim V_j Vi∼Vj的最短路径，则需要顺着 p a t h path path数组往前找。
以上图的 V 2 ∼ V 4 V_2 \sim V_4 V2∼V4顶点为例：
首先 p a t h [ V 2 ] [ V 4 ] = 3 path[V_2][V_4]=3 path[V2][V4]=3，则说明经过 V 3 V_3 V3进行中转，路径为 V 2 → ( V 3 ) → V 4 V_2 \rightarrow (V_3) \rightarrow V_4 V2→(V3)→V4
接着找 p a t h [ V 2 ] [ V 3 ] = 1 path[V_2][V_3]=1 path[V2][V3]=1，则说明经过 V 1 V_1 V1进行中转，路径为 V 2 → ( V 1 ) → V 3 → V 4 V_2 \rightarrow (V_1) \rightarrow V_3 \rightarrow V_4 V2→(V1)→V3→V4
接着找 p a t h [ V 2 ] [ V 1 ] = − 1 path[V_2][V_1]=-1 path[V2][V1]=−1，则说明没有经过任何顶点进行中转，得到最终的路径为 V 2 → V 1 → V 3 → V 4 V_2 \rightarrow V_1 \rightarrow V_3 \rightarrow V_4 V2→V1→V3→V4
给出核心部分的C语言代码：
重庆分公司
重庆分公司
for (k = 0; k< VertexNum; k++) // 将每个顶点都作为中转尝试
{// 遍历整个矩阵 i-行 j-列
for (i = 0; i< VertexNum; i++)
{for (j = 0; j< VertexNum; j++)
{// 若经过k顶点中转，路径更短，则更新矩阵
if (dis[i][k] + dis[k][j]< dis[i][j])
{dis[i][j] = dis[i][k] + dis[k][j]; // 更新dis矩阵
path[i][j] = k; // 更新path矩阵
}
}
}
}空间复杂度 O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)
时间复杂度 O ( ∣ V ∣ 3 ) O(|V|^3) O(∣V∣3)
估计这时候你也看出了一些问题，我使用Dijkstra算法将每个顶点作为起点计算一遍，时间复杂度不也是 O ( ∣ V ∣ 3 ) O(|V|^3) O(∣V∣3)吗？那Floyd算法的优势在哪里呢？
其实，虽然两种算法都是 O ( ∣ V ∣ 3 ) O(|V|^3) O(∣V∣3)，但是前面的系数并不相同，Floyd的系数会更小一些，所有效率也会更高一些。也因此，即使它的复杂度到达了 O ( ∣ V ∣ 3 ) O(|V|^3) O(∣V∣3)的程度，对于一些中小规模的图仍然是适用的。
同时Floyd也支持负权边，也是其一个优点。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
