首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python 学习手册
Python Cookbook
Python 基础教程
Python Sites
PyPI - Python Package Index
http://www.simple-is-better.com/
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
Qzier
V2EX  ›  Python

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

  •  
  •   Qzier · 329 天前 · 684 次点击
    这是一个创建于 329 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    代码如下:

    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

    第 1 条附言  ·  329 天前

    知道区别了,@66450146 说的队,如果不给定终点,两种方法计算所有的顶点是没有区别的。

    但如果要计算起点指定终点的最短路径,我的 BFS 算法中,对于当前顶点,路径不一定是最短路径,需要访问完所有的顶点才能确定最短路径,而 Dijkstra 算法对于当前顶点,走的就是最短路径,不用计算所有顶点。

    最终代码如下:

    from heapq import heappush, heappop
    
    
    def dijkstra(graph, source, destination=None):
        distances = {vertex: float('inf') for vertex in graph}
        distances[source] = 0
    
        priority_queue = [(distances[source], source)]
        precursors = {}
    
        while priority_queue:
            distance, vertex = heappop(priority_queue)
            if distance == distances[vertex]:
                if destination == vertex:
                    break
                for neighbor in graph[vertex]:
                    if distances[vertex] + graph[vertex][neighbor] < distances[neighbor]:
                        distances[neighbor] = distances[vertex] + graph[vertex][neighbor]
                        heappush(priority_queue, (distances[neighbor], neighbor))
                        precursors[neighbor] = vertex
    
        if destination:
            precursor = destination
            path = []
            while precursor:
                path.append(precursor)
                precursor = precursors.get(precursor)
            return distances[destination], path[::-1]
    
        paths = []
        for precursor in precursors:
            path = []
            while precursor:
                path.append(precursor)
                precursor = precursors.get(precursor)
            paths.append(path[::-1])
        return distances, paths
    
    第 2 条附言  ·  329 天前
    刚才看 Bellman-Ford 算法,才发现我写的 bfs 队列版本竟然和 SPFA 的思路是一样的,不过这里没有检测环路,因此对于只有正权边的图是适用的。
    MrAMS
        1
    MrAMS   329 天前
    Dijkstra 本质上其实就是个贪心
    每次要从队列中选取距离最小的顶点出发保证了每一步的最优
    (广度优先搜索出来的,因为数据特殊?)
    Qzier
        2
    Qzier   329 天前
    @MrAMS 我按照广度优先搜索的顺序然后更新每个顶点的距离也不影响结果,试了好多例子。
    Fulcrum
        3
    Fulcrum   329 天前 via Android
    没记错是因为
    P(n)+p(n+1)>=p(x)+p(n+1)?去年学的运筹,基本忘了。。。
    是反证法证明的。
    Fulcrum
        4
    Fulcrum   329 天前 via Android
    没记错是因为
    P(n)+p(n+1)>=p(x)+p(n+1)?去年学的运筹,基本忘了。。。
    是反证法证明的,记得很短。
    建议找本运筹学看看,有证明的
    66450146
        5
    66450146   329 天前   ♥ 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)
    66450146
        6
    66450146   329 天前
    格式乱了,就是加了一个 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}
    }

    得出来的结果是不一样的
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4165 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 22ms · UTC 08:38 · PVG 16:38 · LAX 00:38 · JFK 03:38
    ♥ Do have faith in what you're doing.