Contents

算法笔记-最短路径算法(Bellman-ford)

最短路径算法是一个比较常见的用于查找2点之间最短路径的方案。在工作中,由于涉及要查找2点之间的最短路径的场景,所以特此记录一下

算法思想

美国应用数学家Richard Bellman (理查德.贝尔曼, 动态规划的提出者)于1958 年发表了该算法。此外Lester Ford在1956年也发表了该算法。因此这个算法叫做Bellman-Ford算法。

Bellman-Ford算法是一种基于逐次逼近思想进行最短路径求解的算法。其可以被应用在带负权的有向图中,Bellman-ford 算法比dijkstra算法更具普遍性,因为它对边没有要求,可以处理负权边与负权回路。缺点是时间复杂度过高,高达O(VE), V为顶点数,E为边数。


其核心思想为:对于任意一个具有n个节点的图 𝐺 ,任意两点之间的最短路径至多包含 𝑛−1 条边。因此我们可以反复通过对边的松弛来得到当前图的最短路径。

也就是说:第1轮在对所有的边进行松弛后,得到的是源点最多经过一条边到达其他顶点的最短距离;第2轮在对所有的边进行松弛后,得到的是源点最多经过两条边到达其他顶点的最短距离;第3轮在对所有的边进行松弛后,得到的是源点最多经过一条边到达其他顶点的最短距离……

松弛操作的含义是更新节点之间的最短距离。

分析

Bellman-Ford-Algorithm-1

第一步:创建一个带权重 (可以有负权) 的有向图

Bellman-Ford-Algorithm-2

第二步:选定一个起点(A),将A 到所有节点的 距离都置为 无穷大。

Bellman-Ford-Algorithm-3

第三步:从节点A开始,将节点最短距离更新,比如 A -> B 直接相连,最短距离是 4 ,A->C 直接相连,距离是 2 。

Bellman-Ford-Algorithm-4

第四步:最差的情况下,我们需要 V (节点个数)次这样的操作。一个节点最短路径需要被调整 V 次。

Bellman-Ford-Algorithm-5

第五步:注意右上角的节点 D 是怎么调整的,因为 B -> D (4+2) = 6 , C -> D (2+4) =6 , E->D (6-5)=1 ,所以被更新.

Bellman-Ford-Algorithm-6

第五步:经过最大循环次数 or 所有的顶点都有其路径长度且不再变后,检查是否有负循环。

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
type Edge struct {
	src    int
	dest   int
	weight float64
}
type Graph struct {
	vertices int
	edges    []Edge
}

func InitGraph(vertices int) *Graph {
	return &Graph{
		vertices: vertices,
		edges:    make([]Edge, 0),
	}
}

func (g *Graph) AddEdge(src, dest int, weight float64) {
	g.edges = append(g.edges, Edge{src, dest, weight})
}

func BellmanFord(g *Graph, source int) ([]float64, []int) {
	dist := make([]float64, g.vertices)
	prev := make([]int, g.vertices)
	for i := 0; i < g.vertices; i++ {
		dist[i] = math.Inf(1) // 将所有节点的距离设为 无穷大
		prev[i] = -1          // 保存到节点v最短距离,到v的上一跳是哪个节点
	}
	dist[source] = 0 // 起点的距离为 0

	// Relax edges V - 1 times(i 从 1 开始计数)
	for i := 1; i < g.vertices; i++ {
		for _, edge := range g.edges {
			u := edge.src
			v := edge.dest
			w := edge.weight
			if dist[u]+w < dist[v] {
				dist[v] = dist[u] + w
				prev[v] = u
			}
		}
	}
	
	// Check for negative cycle,经过了 v-1 次循环了,还是存在更短的路径证明存在负环了
	for _, edge := range g.edges {
		u := edge.src
		v := edge.dest
		w := edge.weight
		if dist[u]+w < dist[v] {
			fmt.Println("Graph contains a negative weight cycle")
			return nil, nil
		}
	}

	return dist, prev
}

func PrintShortestPaths(dist []float64, prev []int, source int) {
	fmt.Println("Shortest Paths from vertex", source)
	for i := 0; i < len(dist); i++ {
		if dist[i] == math.Inf(1) {
			fmt.Printf("Vertex %d is not reachable\n", i)
		} else {
			path := []int{}
			j := i
			for j != -1 {
				path = append([]int{j}, path...)
				j = prev[j]
			}
			fmt.Printf("Vertex %d: Distance=%f, Path=%v\n", i, dist[i], path)
		}
	}
}

func main() {
	g := InitGraph(5)

	g.AddEdge(0, 1, 1)
	g.AddEdge(0, 2, 1)
	g.AddEdge(1, 2, 1)
	g.AddEdge(1, 3, 1)
	g.AddEdge(1, 4, 1)
	g.AddEdge(2, 3, 1)
	g.AddEdge(2, 4, 1)
	g.AddEdge(3, 1, 1)
	g.AddEdge(4, 0, 1)
	g.AddEdge(4, 3, 1)

	source := 0
	dist, prev := BellmanFord(g, source)
	if dist != nil && prev != nil {
		PrintShortestPaths(dist, prev, source)
	}
}