How to make Dijkstra's algorithm report the full final distance for that shortest route

Question

I'm relatively new to python and have been reading on the internet on ways to implement Dijkstra's algorithm and I came across the code provided below on this page here.

The code is an implementation of Dijkstra's algorithm and it works perfectly fine. see code below:

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

This is the test data provided:

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

To run it for specific two points, say 'a' to 'e':

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

Output looks like this:

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

My question is this, how can I make this algorithm report the full final distance for that shortest route. i.e. desired output to look something like this:

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

I've been trying adding 'dist' to the append at the end of function 'Dijkstra' but doesn't seem to work, I don't get anything different:

s.appendleft(dist)

It's probably something simple somewhere to tweak but I can't seem to figure it out, any help is highly appreciated.

Thanks.

Answer 1

i think you need to add alt instead of dist.

try this at the end of your function

s.appendleft(alt)