Implement Dijkstra's Shortest PathStep 4 of 5

Numeric distance query

12345

Step 4: Numeric distance query

Expose a clean numeric API. Implement distance(source, target) that returns the shortest distance from source to target as a number, or float('inf') when target cannot be reached.

Reuse the work you already built: call shortest_distances(source) and look up target in the resulting dict, defaulting to infinity when it is absent. This is the kind of one-line query a routing service exposes on top of the core algorithm.

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):
        dist = {source: 0}
        prev = {}
        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
                    prev[v] = u
                    heapq.heappush(pq, (nd, v))
        if target not in dist:
            return []
        path = []
        cur = target
        while cur != source:
            path.append(cur)
            cur = prev[cur]
        path.append(source)
        path.reverse()
        return path

    def distance(self, source, target):
        """Return the numeric shortest distance, or float('inf') if unreachable."""
        # TODO: reuse shortest_distances and look up target
        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