关于这个队列实现的版本中:
为什么每次要从队列中选取距离最小的顶点出发?而不是按照广度优先的顺序?
代码如下:
def dijkstra1(graph, start):
distances = {vertex: float('inf') for vertex in graph}
distances[start] = 0
visited = set()
queue = list(graph.keys())
while queue:
vertex = min(queue, key=lambda vertex: distances[vertex])
queue.remove(vertex)
visited.add(vertex)
for neighbor in graph[vertex]:
if distances[vertex] + graph[vertex][neighbor] < distances[neighbor]:
distances[neighbor] = distances[vertex] + graph[vertex][neighbor]
if neighbor not in visited:
queue.append(neighbor)
return distances
我试着用广度优先搜索,发现也不影响实际结果,而且性能和用最小堆实现的差不多
from collections import deque
def dijkstra2(graph, start):
distances = {vertex: float('inf') for vertex in graph}
distances[start] = 0
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
visited.add(vertex)
for neighbor in graph[vertex]:
if distances[vertex] + graph[vertex][neighbor] < distances[neighbor]:
distances[neighbor] = distances[vertex] + graph[vertex][neighbor]
if neighbor not in visited:
queue.append(neighbor)
return distances
测试代码
g = {
'A': {'B': 3, 'D': 1},
'B': {'A': 3, 'C': 5, 'D': 4, 'E': 5},
'C': {'B': 5, 'E': 9},
'D': {'A': 1, 'B': 4, 'E': 1},
'E': {'B': 5, 'C': 9, 'D': 1}
}
print(dijkstra(g, 'A'))
测试图
这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。
V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。
V2EX is a community of developers, designers and creative people.