Python中的Dijkstra算法
我正在尝试用数组在Python中实现Dijkstra算法。这是我的实现代码。
def extract(Q, w):
m=0
minimum=w[0]
for i in range(len(w)):
if w[i]<minimum:
minimum=w[i]
m=i
return m, Q[m]
def dijkstra(G, s, t='B'):
Q=[s]
p={s:None}
w=[0]
d={}
for i in G:
d[i]=float('inf')
Q.append(i)
w.append(d[i])
d[s]=0
S=[]
n=len(Q)
while Q:
u=extract(Q,w)[1]
S.append(u)
#w.remove(extract(Q, d, w)[0])
Q.remove(u)
for v in G[u]:
if d[v]>=d[u]+G[u][v]:
d[v]=d[u]+G[u][v]
p[v]=u
return d, p
B='B'
A='A'
D='D'
G='G'
E='E'
C='C'
F='F'
G={B:{A:5, D:1, G:2}, A:{B:5, D:3, E:12, F:5}, D:{B:1, G:1, E:1, A:3}, G:{B:2, D:1, C:2}, C:{G:2, E:1, F:16}, E:{A:12, D:1, C:1, F:2}, F:{A:5, E:2, C:16}}
print "Assuming the start vertex to be B:"
print "Shortest distances", dijkstra(G, B)[0]
print "Parents", dijkstra(G, B)[1]
我期望得到的结果是：
Assuming the start vertex to be B:
Shortest distances {'A': 4, 'C': 4, 'B': 0, 'E': 2, 'D': 1, 'G': 2, 'F': 4}
Parents {'A': 'D', 'C': 'G', 'B': None, 'E': 'D', 'D': 'B', 'G': 'D', 'F': 'E'}
但是，我得到的结果却是：
Assuming the start vertex to be B:
Shortest distances {'A': 4, 'C': 4, 'B': 0, 'E': 2, 'D': 1, 'G': 2, 'F': 10}
Parents {'A': 'D', 'C': 'G', 'B': None, 'E': 'D', 'D': 'B', 'G': 'D', 'F': 'A'}.
对于节点F，程序给出的答案不正确。有人能告诉我这是为什么吗？
13 个回答
8
这不是我的答案——我的教授做得比我尝试的要高效得多。这里是他的做法，显然使用了辅助函数来处理那些重复的任务。
def dijkstra(graph, source):
vertices, edges = graph
dist = dict()
previous = dict()
for vertex in vertices:
dist[vertex] = float("inf")
previous[vertex] = None
dist[source] = 0
Q = set(vertices)
while len(Q) > 0:
u = minimum_distance(dist, Q)
print('Currently considering', u, 'with a distance of', dist[u])
Q.remove(u)
if dist[u] == float('inf'):
break
n = get_neighbours(graph, u)
for vertex in n:
alt = dist[u] + dist_between(graph, u, vertex)
if alt < dist[vertex]:
dist[vertex] = alt
previous[vertex] = u
return previous
给定一个图
({'A', 'B', 'C', 'D'}, {('A', 'B', 5), ('B', 'A', 5), ('B', 'C', 10), ('B', 'D', 6), ('C', 'D', 2), ('D', 'C', 2)})
命令 print(dijkstra(graph, 'A') 的输出是
当前考虑 A，距离为 0
当前考虑 B，距离为 5
当前考虑 D，距离为 11
当前考虑 C，距离为 13
也就是说：
{'C': 'D', 'D': 'B', 'A': None, 'B': 'A'} => 顺序是随机的
10
我需要一个能返回路径的解决方案，所以我结合了多个问题和答案的思路，写了一个简单的类，使用了迪杰斯特拉算法：
class Dijkstra:
def __init__(self, vertices, graph):
self.vertices = vertices # ("A", "B", "C" ...)
self.graph = graph # {"A": {"B": 1}, "B": {"A": 3, "C": 5} ...}
def find_route(self, start, end):
unvisited = {n: float("inf") for n in self.vertices}
unvisited[start] = 0 # set start vertex to 0
visited = {} # list of all visited nodes
parents = {} # predecessors
while unvisited:
min_vertex = min(unvisited, key=unvisited.get) # get smallest distance
for neighbour, _ in self.graph.get(min_vertex, {}).items():
if neighbour in visited:
continue
new_distance = unvisited[min_vertex] + self.graph[min_vertex].get(neighbour, float("inf"))
if new_distance < unvisited[neighbour]:
unvisited[neighbour] = new_distance
parents[neighbour] = min_vertex
visited[min_vertex] = unvisited[min_vertex]
unvisited.pop(min_vertex)
if min_vertex == end:
break
return parents, visited
@staticmethod
def generate_path(parents, start, end):
path = [end]
while True:
key = parents[path[0]]
path.insert(0, key)
if key == start:
break
return path
下面是一个示例图和使用方法（这个图是用一个很棒的工具生成的）：
input_vertices = ("A", "B", "C", "D", "E", "F", "G")
input_graph = {
"A": {"B": 5, "D": 3, "E": 12, "F": 5},
"B": {"A": 5, "D": 1, "G": 2},
"C": {"E": 1, "F": 16, "G": 2},
"D": {"A": 3, "B": 1, "E": 1, "G": 1},
"E": {"A": 12, "C": 1, "D": 1, "F": 2},
"F": {"A": 5, "C": 16, "E": 2},
"G": {"B": 2, "C": 2, "D": 1}
}
start_vertex = "B"
end_vertex= "C"
dijkstra = Dijkstra(input_vertices, input_graph)
p, v = dijkstra.find_route(start_vertex, end_vertex)
print("Distance from %s to %s is: %.2f" % (start_vertex, end_vertex, v[end_vertex]))
se = dijkstra.generate_path(p, start_vertex, end_vertex)
print("Path from %s to %s is: %s" % (start_vertex, end_vertex, " -> ".join(se)))
输出结果
Distance from B to C is: 3.00
Path from B to C is: B -> D -> E -> C
12
我把它写得更详细一些，以便让初学者更容易理解：
def get_parent(pos):
return (pos + 1) // 2 - 1
def get_children(pos):
right = (pos + 1) * 2
left = right - 1
return left, right
def swap(array, a, b):
array[a], array[b] = array[b], array[a]
class Heap:
def __init__(self):
self._array = []
def peek(self):
return self._array[0] if self._array else None
def _get_smallest_child(self, parent):
return min([
it
for it in get_children(parent)
if it < len(self._array)
], key=lambda it: self._array[it], default=-1)
def _sift_down(self):
parent = 0
smallest = self._get_smallest_child(parent)
while smallest != -1 and self._array[smallest] < self._array[parent]:
swap(self._array, smallest, parent)
parent, smallest = smallest, self._get_smallest_child(smallest)
def pop(self):
if not self._array:
return None
swap(self._array, 0, len(self._array) - 1)
node = self._array.pop()
self._sift_down()
return node
def _sift_up(self):
index = len(self._array) - 1
parent = get_parent(index)
while parent != -1 and self._array[index] < self._array[parent]:
swap(self._array, index, parent)
index, parent = parent, get_parent(parent)
def add(self, item):
self._array.append(item)
self._sift_up()
def __bool__(self):
return bool(self._array)
def backtrack(best_parents, start, end):
if end not in best_parents:
return None
cursor = end
path = [cursor]
while cursor in best_parents:
cursor = best_parents[cursor]
path.append(cursor)
if cursor == start:
return list(reversed(path))
return None
def dijkstra(weighted_graph, start, end):
"""
Calculate the shortest path for a directed weighted graph.
Node can be virtually any hashable datatype.
:param start: starting node
:param end: ending node
:param weighted_graph: {"node1": {"node2": weight, ...}, ...}
:return: ["START", ... nodes between ..., "END"] or None, if there is no
path
"""
distances = {i: float("inf") for i in weighted_graph}
best_parents = {i: None for i in weighted_graph}
to_visit = Heap()
to_visit.add((0, start))
distances[start] = 0
visited = set()
while to_visit:
src_distance, source = to_visit.pop()
if src_distance > distances[source]:
continue
if source == end:
break
visited.add(source)
for target, distance in weighted_graph[source].items():
if target in visited:
continue
new_dist = distances[source] + weighted_graph[source][target]
if distances[target] > new_dist:
distances[target] = new_dist
best_parents[target] = source
to_visit.add((new_dist, target))
return backtrack(best_parents, start, end)
20
这个实现只使用了数组和堆这种数据结构。
import heapq as hq
import math
def dijkstra(G, s):
n = len(G)
visited = [False]*n
weights = [math.inf]*n
path = [None]*n
queue = []
weights[s] = 0
hq.heappush(queue, (0, s))
while len(queue) > 0:
g, u = hq.heappop(queue)
visited[u] = True
for v, w in G[u]:
if not visited[v]:
f = g + w
if f < weights[v]:
weights[v] = f
path[v] = u
hq.heappush(queue, (f, v))
return path, weights
G = [[(1, 6), (3, 7)],
[(2, 5), (3, 8), (4, -4)],
[(1, -2), (4, 7)],
[(2, -3), (4, 9)],
[(0, 2)]]
print(dijkstra(G, 0))
我希望这能帮助到某个人，虽然有点晚了。
45
正如其他人提到的，由于没有使用易懂的变量名，调试你的代码几乎是不可能的。
根据维基百科上关于迪杰斯特拉算法的文章，你可以按照以下方式来实现它（当然还有很多其他的方法）：
nodes = ('A', 'B', 'C', 'D', 'E', 'F', 'G')
distances = {
'B': {'A': 5, 'D': 1, 'G': 2},
'A': {'B': 5, 'D': 3, 'E': 12, 'F' :5},
'D': {'B': 1, 'G': 1, 'E': 1, 'A': 3},
'G': {'B': 2, 'D': 1, 'C': 2},
'C': {'G': 2, 'E': 1, 'F': 16},
'E': {'A': 12, 'D': 1, 'C': 1, 'F': 2},
'F': {'A': 5, 'E': 2, 'C': 16}}
unvisited = {node: None for node in nodes} #using None as +inf
visited = {}
current = 'B'
currentDistance = 0
unvisited[current] = currentDistance
while True:
for neighbour, distance in distances[current].items():
if neighbour not in unvisited: continue
newDistance = currentDistance + distance
if unvisited[neighbour] is None or unvisited[neighbour] > newDistance:
unvisited[neighbour] = newDistance
visited[current] = currentDistance
del unvisited[current]
if not unvisited: break
candidates = [node for node in unvisited.items() if node[1]]
current, currentDistance = sorted(candidates, key = lambda x: x[1])[0]
print(visited)
这段代码比必要的要啰嗦一些，我希望你能通过对比你的代码和我的代码，发现一些不同之处。
结果是：
{'E': 2, 'D': 1, 'G': 2, 'F': 4, 'A': 4, 'C': 3, 'B': 0}