Implement Dijkstra's Shortest PathStep 2 of 5

Shortest distances with Dijkstra

12345

Step 2: Shortest distances with Dijkstra

Now compute the shortest distance from a source to every reachable node. This is exactly what a router does to learn the lowest-latency cost to reach each destination.

Implement shortest_distances(source) using Dijkstra's algorithm:

  • Keep a dict dist of the best known distance per node, starting with dist[source] = 0.
  • Use a min-heap (heapq) of (distance, node) tuples. Pushing the distance first keeps the ordering deterministic and pops the closest node next.
  • When you pop a node whose recorded distance is stale (larger than dist for that node), skip it.
  • Relax each outgoing edge: if going through the current node reaches a neighbor more cheaply, update dist and push the neighbor.

Return the dist dict. Unreachable nodes are simply omitted from the dict (callers treat a missing node as infinity). All weights are non-negative.

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):
        """Return dict of node -> shortest distance from source (Dijkstra)."""
        # TODO: run Dijkstra with a heap and return the distance dict
        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