Implement Dijkstra's Shortest PathStep 3 of 5

Reconstruct the shortest path

12345

Step 3: Reconstruct the shortest path

Knowing the distance is not enough for a map: you need the actual sequence of hops. Implement shortest_path(source, target) that returns the list of nodes on a shortest path from source to target, or [] when target is unreachable.

Run the same Dijkstra loop, but also keep a prev dict mapping each node to the node you arrived from whenever you relax an edge. After the loop:

  • If target was never reached, return [].
  • Otherwise walk backward from target through prev until you reach source, then reverse the collected nodes so the path runs source to target.

For source == target the path is just [source].

Hints
Starter code
import heapq


class WeightedGraph:
    def __init__(self):
        self.adj = {}

    def add_edge(self, u, v, w):
        if u not in self.adj:
            self.adj[u] = []
        self.adj[u].append((v, w))

    def neighbors(self, u):
        return self.adj.get(u, [])

    def shortest_distances(self, source):
        dist = {source: 0}
        pq = [(0, source)]
        while pq:
            d, u = heapq.heappop(pq)
            if d > dist.get(u, float("inf")):
                continue
            for v, w in self.neighbors(u):
                nd = d + w
                if nd < dist.get(v, float("inf")):
                    dist[v] = nd
                    heapq.heappush(pq, (nd, v))
        return dist

    def shortest_path(self, source, target):
        """Return the list of nodes on a shortest path, or [] if unreachable."""
        # TODO: track predecessors during Dijkstra, then reconstruct the path
        pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step