50. Min-Latency Service Path

Problem

A single query can be routed through alternative chains of retrieval, rerank, and generation service instances. Each directed edge between two service nodes has a latency cost (always non-negative). Given the routing graph and a source and destination service node, find the minimum total latency of any path from the source to the destination.

If no path exists, return infinity. If the source and destination are the same node, the answer is 0. All edge weights are guaranteed non-negative, which is what makes Dijkstra's algorithm applicable (it does not handle negative edge weights correctly).

Source: src/50_min_latency_service_path.py

def min_latency_path(n: int, edges: list[tuple[int, int, float]], src: int, dst: int) -> float:
    # edges is a list of (u, v, weight) directed edges over n nodes numbered 0..n-1

>>> min_latency_path(n=5, edges=[(0, 1, 4.0), (0, 2, 1.0), (2, 1, 2.0), (1, 3, 1.0), (2, 3, 5.0), (3, 4, 3.0)], src=0, dst=4)
7.0

>>> min_latency_path(n=3, edges=[(0, 1, 1.0)], src=0, dst=2)
inf

Step-by-Step Approach

1. Handle the trivial case first: if src == dst, the minimum latency is 0.0 regardless of the graph.
2. Build an adjacency list graph[u] = [(v, weight), ...] from the edge list for O(1) neighbor lookups during traversal.
3. Initialize a dist array of size n to infinity for every node except dist[src] = 0.0.
4. Use a min-heap (priority queue) seeded with (0.0, src), always popping the node with the smallest known tentative distance next.
5. When popping (d, u), skip it if d > dist[u] (a stale heap entry from before a better path to u was found). If u == dst, the popped distance is final — return it immediately.
6. Otherwise, relax every outgoing edge (u, v, w): if d + w < dist[v], update dist[v] and push (d + w, v) onto the heap.
7. If the heap empties without ever popping dst, return dist[dst], which remains infinity if dst is unreachable.

The key insight is the greedy correctness argument: because all edge weights are non-negative, the first time a node is popped from the min-heap, its tentative distance is guaranteed to be the true shortest distance — no later-discovered path could ever be shorter, since adding more non-negative edges can't decrease a total.

Reference solution

import heapq


def min_latency_path(n: int, edges: list[tuple[int, int, float]], src: int, dst: int) -> float:
    # Dijkstra's algorithm with a min-heap, O((V + E) log V) time
    if src == dst:
        # trivial-case shortcut
        return 0.0
    graph: list[list[tuple[int, float]]] = [[] for _ in range(n)]
    for u, v, w in edges:
        graph[u].append((v, w))
    # unreached nodes start at infinity
    dist = [float("inf")] * n
    dist[src] = 0.0
    heap: list[tuple[float, int]] = [(0.0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            # stale heap entry (lazy deletion) — a shorter path already won
            continue
        if u == dst:
            # first pop of dst is the true shortest distance (non-negative weights)
            return d
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                # push a fresh entry instead of decrease-key
                heapq.heappush(heap, (nd, v))
    return dist[dst]

Key Functions & Tricks

• import heapq — Python's built-in binary min-heap, operating in place on a plain list.
• heapq.heappush(heap, (nd, v)) — pushes and re-sifts to maintain heap order, O(log n).
• heapq.heappop(heap) — pops the smallest (distance, node) tuple, O(log n).
• float("inf") — initial tentative distance for every node before it's reached.
• Lazy deletion (stale heap entries) — the key trick: never decrease-key, just push a better tuple and skip stale pops via if d > dist[u]: continue.
• Early-exit on popping the destination — non-negative weights guarantee the first pop of dst is shortest.
• Edge relaxation: if nd < dist[v]: ... — update and re-push only if strictly better.
• if src == dst: return 0.0 — trivial-case shortcut, skips building the graph.

How to Recognize This Pattern