最短路径算法-Floyd

注:本文已发布超过一年,请注意您所使用工具的相关版本是否适用

在上一篇当中讲了 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 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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)
}
}

关注我获取更新

wechat
知乎
github

猜你喜欢


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议,转载请注明出处,禁止全文转载