最短路径算法-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
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)
}
}