最短路径算法
最短路径问题
输入:一个有权图G=(V,E)
- 边可以有向也可以无向
- 有时候,我们允许负边权重
- 注:未加权图使用BFS(广度优先搜索代码)
输出:两个给定节点u
和v
之间路径的总权重(消费,长度)
- 有时,我们需要计算所有对最短路径
- 有时,我们需要计算从
u
到其他所有节点的最短路径
概述
- Floyd-Warshall Algorithm
- Dijkstra’s Algorithm
Floyd-Warshall
- 给定一个有向权重图G
- 输出矩阵D,其中dij是距离节点i至j
- 可以检测到负重循环
- 时间复杂度O(x3)
- 非常容易编码
伪代码
- 将D初始化为给定的成本矩阵
For = 1,...,n :
For all i and j :
- dij= min(dij,dik+dki)
- 对于i和j,if dij + dji < 0,则这个图存在负权循环
- 我们怎么运行
原理
- 定义
f(i,j,k)
作为i到j的最小路径,使用节点1,...,k作为中间节点 f(i,j,n)
为i到j的最小路径f(i,j,0)
= cost(i,j)
f(i,j,k)
的最佳路径可以有k作为中间节点,也可以没有k做为中间节点 - 如果有,
f(i,j,k) = f(i,k,k − 1) + f(k,j,k − 1)
- 没有,
f(i,j,k)=f(i,j,k−1)
- 因此,
f(i,j,k)
就是上述两个量中的最小值 - 我们有了以下结果和通用案例
f(i,j,0) = cost(i,j)
f(i,j,k) = min(f(i,k,k − 1) + f(k,j,k − 1),f(i,j,k − 1))
- 对于
f(·,·,k−1)
的值,我们可以计算f(·,·,k)
- 结果表明,我们不需要为每个k单独使用一个矩阵,可以覆盖现有值
- 这就是我们获取
Floyd-Warshall algorithm
Floyd案例
- 案例图示
- 转换成邻接矩阵
+∞(BA,6)(CA,3)(AB,4)+∞+∞(AC,11)(BC,2)+∞
开始加入中间节点
- 加入A节点,CB之间因为A的加入从无穷缩小到7
+∞(BA,6)(CA,3)(AB,4)+∞(CAB,7)(AC,11)(BC,2)+∞
- 加入B节点,AC之间因为B的加入从无穷缩小到6
+∞(BA,6)(CA,3)(AB,4)+∞(CAB,7)(ABC,6)(BC,2)+∞
- 加入C节点,BA之间因为C的加入从无穷缩小到5
+∞(BCA,5)(CA,3)(AB,4)+∞(CAB,7)(ABC,6)(BC,2)+∞
Dijkstra
- 给定有向权重图G和一个源点s
- 输出一个矢量d,di是从源头s到节点i
- 时间负责度依赖于实现
- 可能为O(n2 + m) , O(lgn + m), O(n lgn + m)
- 特别像
Prim
算法 - 发现靠近源头s的最近节点,然后是第二个最近,然后第三个,等
- 维持一个set集合,命名为S,其保存可以到达的最小路径节点
- 一个矢量d,从源头算出的最小距离
- 初始化,S:={s},并且dv := cost(s,v)
- 重复直到S = V
- 查找v ∈/ S,并且存在dv,将其加入到S
- 迭代边 v -> u ,并计算花费c:
- du := min (du , dv + c)
Dijkstra案例
Dijkstra案例解析
S = {v0},T = {v1,v2,v3,v4,v5,v6}
- 从v0出发找到与T集合之间的最小的边(可以直接连接,也可以是节点加入回溯所得),从这里我们选择v2,
v0->v2 = 8
加入S = {v0,v2}
开始 | 结束 | 距离 | 路径 |
---|
v0 | v1 | 13 | v0,v1 |
v0 | v2 | 8 | v0,v2 |
v0 | v3 | ∞ | |
v0 | v4 | 30 | v0,v4 |
v0 | v5 | ∞ | |
v0 | v6 | 32 | v0,v6 |
- 从v0出发,判断是否有距离缩短,从这里我们选择v1/v3
v0->v1 = 13
,加入S = {v0,v1,v2}
开始 | 结束 | 距离 | 路径 |
---|
v0 | v1 | 13 | v0,v1 |
v0 | v3 | 13 | v0,v2,v3 |
v0 | v4 | 30 | v0,v4 |
v0 | v5 | ∞ | |
v0 | v6 | 32 | v0,v6 |
- 从v0出发,判断是否有距离缩短,选择v3加入
S = {v0,v1,v2,v3}
开始 | 结束 | 距离 | 路径 |
---|
v0 | v3 | 13 | v0,v2,v3 |
v0 | v4 | 30 | v0,v4 |
v0 | v5 | 22 | v0,v1,v5 |
v0 | v6 | 32 | v0,v6 |
- 从v0出发,判断是否有距离缩短,选择v4加入
S = {v0,v1,v2,v3,v4}
开始 | 结束 | 距离 | 路径 |
---|
v0 | v4 | 19 | v0,v2,v3,v4 |
v0 | v5 | 22 | v0,v1,v5 |
v0 | v6 | 20 | v0,v1,v6 |
- 从v0出发,判断是否有距离缩短,选择v6,加入
S = {v0,v1,v2,v3,v4,v6}
开始 | 结束 | 距离 | 路径 |
---|
v0 | v5 | 21 | v0,v2,v3,v4,v5 |
v0 | v6 | 20 | v0,v1,v6 |
- 从v0出发,判断是否有距离缩短,加入v5,S = V
开始 | 结束 | 距离 | 路径 |
---|
v0 | v5 | 21 | v0,v2,v3,v4,v5 |