图相关文章：
1. 图的建立 - 邻接矩阵与邻接表
2. 图的遍历 - DFS与BFS
3. 顶点度的计算
4. 最小生成树 - Prim与Kruskal
5. 单源最短路径 - Dijkstra与Bellman-Ford
6. 多源最短路径 - Floyd
7. 拓扑排序AOV网
创新互联专业为企业提供
常宁网站建设、常宁做网站、常宁网站设计、常宁网站制作等企业网站建设、网页设计与制作、常宁企业网站模板建站服务，10多年
常宁做网站经验，不只是建网站，更提供有价值的思路和整体网络服务。
文章目录
Floyd算法
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作为中转结点，求得各顶点间最终的最短路径。
3.1 算法思想
Floyd只能使用邻接矩阵来实现。
为了方便理解，我们来手动模拟一下实现过程。以有向图演示，无向图同理。
我们使用两个大小为
n
×
n
n \times n
n×n的二维数组分别记录最短路径
d
i
s
dis
dis与中转顶点
p
a
t
h
path
path。其中，最短路径矩阵可以告诉我们任意两顶点间的最短距离；而中转顶点矩阵可以告诉我们路径。
（1）初始化
初始化的最短路径矩阵其实就是邻接矩阵，中转顶点矩阵全部标记为
−
1
-1
−1，代表未经过中转。
（2）求解
① 加入
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，故不会进行更新，且已经将所有顶点中转完成，得到的便是最终结果。
（3）输出
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
3.2 实现
给出核心部分的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矩阵
}
}
}
}
3.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元起，快前往官网查看详情吧
本文标题：【图】（六）多源最短路径-Floyd详解-C语言-创新互联
网址分享：
http://cdkjz.cn/article/dshjhc.html
