python - 如何使 Dijkstra 算法报告最短路线的完整最终距离

Question

我对 python 比较陌生，一直在互联网上阅读有关实现 Dijkstra 算法的方法，并且我遇到了本页 here 下面提供的代码。 .

该代码是 Dijkstra 算法的实现，并且运行得非常好。参见下面的代码:

from collections import namedtuple, deque
from pprint import pprint as pp


inf = float('inf')
Edge = namedtuple('Edge', ['start', 'end', 'cost'])

class Graph():
    def __init__(self, edges):
        self.edges = [Edge(*edge) for edge in edges]
        # print(dir(self.edges[0]))
        self.vertices = {e.start for e in self.edges} | {e.end for e in self.edges}

    def dijkstra(self, source, dest):
        assert source in self.vertices
        dist = {vertex: inf for vertex in self.vertices}
        previous = {vertex: None for vertex in self.vertices}
        dist[source] = 0
        q = self.vertices.copy()
        neighbours = {vertex: set() for vertex in self.vertices}
        for start, end, cost in self.edges:
        neighbours[start].add((end, cost))
        #pp(neighbours)

        while q:
            # pp(q)
            u = min(q, key=lambda vertex: dist[vertex])
            q.remove(u)
            if dist[u] == inf or u == dest:
                break
            for v, cost in neighbours[u]:
                alt = dist[u] + cost
                if alt < dist[v]:                                  # Relax (u,v,a)
                dist[v] = alt
                previous[v] = u
        #pp(previous)
        s, u = deque(), dest
        while previous[u]:
            s.appendleft(u)
            u = previous[u]
        s.appendleft(u)
        return s

这是提供的测试数据:

graph = Graph([("a", "b", 7),  ("a", "c", 9),  ("a", "f", 14), ("b", "c", 10),
           ("b", "d", 15), ("c", "d", 11), ("c", "f", 2),  ("d", "e", 6),
           ("e", "f", 9)])

要针对特定​​的两个点运行它，请说“a”到“e”:

pp(graph.dijkstra("a", "e"))

输出如下:

deque(['a', 'c', 'd', 'e'])

我的问题是，如何让该算法报告该最短路线的完整最终距离。即期望的输出看起来像这样:

deque(['FullDistance', 'a', 'c', 'd', 'e'])

我一直在尝试将“dist”添加到函数“Dijkstra”末尾的附加中，但似乎不起作用，我没有得到任何不同的结果:

s.appendleft(dist)

这可能是一些简单的需要调整的地方，但我似乎无法弄清楚，非常感谢任何帮助。

谢谢。

Answer 1

我认为你需要添加 alt 而不是 dist。

在函数末尾尝试这个

s.appendleft(alt)