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

2019-02-23 19:50:44 +08:00
 Qzier

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

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

代码如下:

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

测试图

1627 次点击
所在节点    Python
6 条回复
MrAMS
2019-02-23 20:05:50 +08:00
Dijkstra 本质上其实就是个贪心
每次要从队列中选取距离最小的顶点出发保证了每一步的最优
(广度优先搜索出来的,因为数据特殊?)
Qzier
2019-02-23 20:10:07 +08:00
@MrAMS 我按照广度优先搜索的顺序然后更新每个顶点的距离也不影响结果,试了好多例子。
Fulcrum
2019-02-23 20:13:56 +08:00
没记错是因为
P(n)+p(n+1)>=p(x)+p(n+1)?去年学的运筹,基本忘了。。。
是反证法证明的。
Fulcrum
2019-02-23 20:14:15 +08:00
没记错是因为
P(n)+p(n+1)>=p(x)+p(n+1)?去年学的运筹,基本忘了。。。
是反证法证明的,记得很短。
建议找本运筹学看看,有证明的
66450146
2019-02-23 21:15:26 +08:00
这是使用场景不合适,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)
66450146
2019-02-23 21:16:52 +08:00
格式乱了,就是加了一个 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}
}

得出来的结果是不一样的

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/538020

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX