Fork me on GitHub

Dijkstra算法与Bellman-Ford算法

Dijkstra算法与Bellman-Ford算法

两者都可以用来寻找加权图中最快的路径,区别在于:

  • Dijkstra算法在无负权边时比BF更快,因为前者仅对每个节点进行遍历,而后者需要对所有的边遍历至多(节点数-1)次。
  • Dijkstra无法处理存在负权边时的问题。
  • BF可以用来判断图中是否存在负权环(表现为迭代次数超过了(节点数-1))。但无法处理含负权环的图。

个人理解:

  • Dijkstra算法是对每个节点遍历,对比大小并判断是否需要更新其邻居(即其指向的节点)的开销(起点到该节点的总权值)。记录各节点的父级节点,通过从终点依次寻找父级节点来得到一条最快路径。因为可能图中存在环,为避免死循环的发生,我们每处理一个节点都将其放入一个特定列表,仅处理列表外的节点。
  • BF算法,起初我以为它是基于Dijkstra的,仔细理解之后我才体会到区别。BF所做的是一次有一次遍历所有的边,相较于Dijkstra而言实现更为简单,由于每遍历一次都至少能找出一条两点间的最短路径,而最短路径的深度不会超过(节点数-1)(即所有节点都在一条路径上的情况),所以遍历次数不会超过(节点数-1)。

下面放上基于python对两种算法的实现:

Dijkstra:

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
def find_lowest_cost_node(costs):
lowest_cost = inf
lowest_cost_node = None
for node in costs:
cost = costs[node]
if cost < lowest_cost and node not in processed:
lowest_cost = cost
lowest_cost_node = node
return lowest_cost_node


def dijkstra():
node = find_lowest_cost_node(costs)
while node is not None:
cost = costs[node]
neighbors = graph[node]
for n in neighbors.keys():
new_cost = cost + neighbors[n]
if new_cost < costs[n]:
costs[n] = new_cost
parents[n] = node
processed.append(node)
node = find_lowest_cost_node(costs)


def print_way():
key = 'fin'
way = []
while parents[key] != 'start':
if key == 'fin':
way.append(key)
key = parents[key]
else:
way.append(key)
key = parents[key]
way.append(key)
way.append('start')
way.reverse()
for w in way:
if w == 'start':
print(w, end='')
else:
print('-->' + w, end='')
print()
print("This way cost " + str(costs['fin']))


if __name__ == '__main__':
# 存储各节点的邻居,与其权重
graph = {'start': {'a': 6,
'b': 2}, 'a': {'fin': 1}, 'b': {'a': 3,
'fin': 5}, 'fin': {}}
'''
# 下为存在负权边时测试用数据,会发现fin对应的开销是35,而并非实际的33。
graph = {'start': {'a': 5, 'b': 0}, 'a': {'b': -7}, 'b': {'fin': 35}, 'fin': {}}
'''

inf = float('inf')
# 存储各节点的开销
costs = {'start': 0, 'a': inf, 'b': inf, 'fin': inf}

# 存储到各节点最小开销时,其父节点名称
parents = {'a': None, 'b': None, 'fin': None}

# 存储已经处理过的节点
processed = []

# 计算部分:
dijkstra()
print_way()

Bellman-Ford:

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
def dic(j, k, l):
d = dict(j=j, k=k, l=l)
return d


def bellman_ford():
for i in range(len(graph.keys()) - 1):
for e in edge:
# line为包含该边起始点、终末点以及长度的字典
line = edge[e]
j = line['j']
k = line['k']
l = line['l']
# cost为该边终末点的开销
cost = costs[k]
new_cost = l + costs[j]
if cost > new_cost:
costs[k] = new_cost
parents[k] = j


def print_way():
key = 'fin'
way = []
while parents[key] != 'start':
if key == 'fin':
way.append(key)
key = parents[key]
else:
way.append(key)
key = parents[key]
way.append(key)
way.append('start')
way.reverse()
for w in way:
if w == 'start':
print(w, end='')
else:
print('-->' + w, end='')
print()
print("This way cost " + str(costs['fin']))


if __name__ == '__main__':
graph = {'start': {'a': 5, 'b': 0}, 'a': {'b': -7}, 'b': {'fin': 35}, 'fin': {}}
inf = float('inf')
costs = {'start': 0, 'a': inf, 'b': inf, 'fin': inf}
parents = {'a': None, 'b': None, 'fin': None}
way = []
edge = {'sa': dic('start', 'a', 5), 'sb': dic('start', 'b', 0), 'ab': dic('a', 'b', -7), 'bf': dic('b', 'fin', 35)}
bellman_ford()
print_way()
欢迎投喂,但你的支持就是对我最佳的回馈。