Python中关于求最短路径的 Dijkstra 算法，有一点困惑

关于这个队列实现的版本中：

为什么每次要从队列中选取距离最小的顶点出发？而不是按照广度优先的顺序？

代码如下：

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’))

测试图

image1.png


Python中关于求最短路径的 Dijkstra 算法，有一点困惑

7 回复

Dijkstra 本质上其实就是个贪心
每次要从队列中选取距离最小的顶点出发保证了每一步的最优
（广度优先搜索出来的，因为数据特殊？）


我无法理解你的问题

我按照广度优先搜索的顺序然后更新每个顶点的距离也不影响结果，试了好多例子。

没记错是因为
P(n)+p(n+1)>=p(x)+p(n+1)？去年学的运筹，基本忘了。。。
是反证法证明的。

没记错是因为
P(n)+p(n+1)>=p(x)+p(n+1)？去年学的运筹，基本忘了。。。
是反证法证明的，记得很短。
建议找本运筹学看看，有证明的

这是使用场景不合适，Dijkstra 更适合你只关心从 A->E 的距离，而不关心到其他节点距离的时候。具体的做法就是在中间提早 return，可以证出来 Dijkstra 得出的一定是最优解，而 BFS 的做法不一定

def dijkstra1(graph, start, end):
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 == end:
return distances[neighbor]
if neighbor not in visited:
queue.append(neighbor)

格式乱了，就是加了一个 if … return 而已，两种做法对于：

g = {
‘A’: {‘B’: 1, ‘F’: 99},
‘B’: {‘A’: 1, ‘C’: 1},
‘C’: {‘B’: 1, ‘D’: 1},
‘D’: {‘C’: 1, ‘E’: 1},
‘E’: {‘D’: 1, ‘F’: 99},
‘F’: {‘A’: 99, ‘E’: 99}
}

得出来的结果是不一样的

回到顶部