在上一篇当中讲了 Dijkstra 算法,Dijkstra 适用于对于单源路径的求取,但是对于任意两个点之间的最小路径呢?首先想到的当然是直接使用多次的 Dijkstra 算法来求取任意两点之间的最短路径,但是这样下来时间复杂度会比较大,所以使用一种新的算法,Floyd 算法来求取最短路径
原理
Floyd 算法是一个经典的动态规划算法。用通俗的语言来描述的话,首先我们的目标是寻找从点 i 到点 j 的最短路径。从动态规划的角度看问题,我们需要为这个目标重新做一个诠释
从任意节点 i 到任意节点 j 的最短路径不外乎 2 种可能:
1.直接从 i 到 j,
2.从 i 经过若干个节点 k 到 j。
所以,我们假设 Dis(i,j)为节点 u 到节点 v 的最短路径的距离,对于每一个节点 k,我们检查 Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立,如果成立,证明从 i 到 k 再到 j 的路径比 i 直接到 j 的路径短,我们便设置 Dis(i,j) = Dis(i,k) + Dis(k,j),这样一来,当我们遍历完所有节点 k,Dis(i,j)中记录的便是 i 到 j 的最短路径的距离。
算法描述:
a.从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。
b.对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
Golang 实现
package ShortestPath
import (
"errors"
"github.com/mohuishou/algorithm/GraphMatrix"
)
//Floyd 求取多源最短路径
func Floyd(graph GraphMatrix.Graph, dist[][] GraphMatrix.EdgeType, path[][] int) error {
for i: = 0;
i < graph.VNum;
i++{
for j: = 0;
j < graph.VNum;
j++{
path[i][j] = -1
dist[i][j] = graph.G[i][j]
}
}
//注意,k必须放在最外层,如果放在最里层会过早的确认两点的最短路径
for k: = 0;
k < graph.VNum;
k++{
for i: = 0;
i < graph.VNum;
i++{
for j: = 0;
j < graph.VNum;
j++{
//找到更短的路径
if dist[i][k] + dist[k][j] < dist[i][j] {
dist[i][j] = dist[i][k] + dist[k][j]
//发现负值圈
if i == j && dist[i][j] < 0 {
return errors.New("存在负值圈")
}
path[i][j] = k
}
}
}
}
return nil
}
//GetPathForFloyd 获取路径
func GetPathForFloyd(path[][] int, s, t int)(tPath[] int) {
tPath = make([] int, 1)
tPath[0] = s
for {
s = path[s][t]
if s == -1 || s == t {
tPath = append(tPath, t)
return tPath
}
tPath = append(tPath, s)
}
}