50. Min-Latency Path Through a Multi-Region Service Graph

Problem

A request can hop through several regional service/inference nodes on its way from a client region to the model-serving node that will handle it, with each hop carrying a fixed network latency in milliseconds. Find the minimum total latency from a source node to a destination node.

n nodes are labeled 0..n-1. edges is a list of directed (u, v, latency_ms) triples. Return the minimum total latency to go from src to dst, or -1 if dst is unreachable. All latencies are non-negative.

Source: src/50_min_latency_service_path.py

def min_latency_path(n: int, edges: list[tuple[int, int, int]], src: int, dst: int) -> int:

>>> min_latency_path(4, [(0, 1, 10), (0, 2, 5), (2, 1, 2), (1, 3, 1), (2, 3, 9)], 0, 3)
8

>>> min_latency_path(3, [(0, 1, 4)], 0, 2)
-1

Step-by-Step Approach

1. Recognize the shape: a directed graph, non-negative edge weights, and a single-source-to-single-destination minimum-total-weight question — the textbook case for Dijkstra's algorithm.
2. Build an adjacency list from the edge triples so each node's outgoing hops and their latencies can be looked up in O(1) amortized time.
3. Maintain a dist array initialized to infinity for every node except src, which starts at 0, and a min-heap seeded with (0, src).
4. Repeatedly pop the node with the smallest tentative distance. If it's a stale entry (a shorter distance was already recorded), skip it — this is cheaper than trying to remove stale entries from the heap directly.
5. For each outgoing edge from the popped node, compute the distance through it; if that's an improvement, update dist and push the new candidate onto the heap. This step is called "relaxing" the edge.
6. Because the heap always pops the globally smallest tentative distance next, once a node is popped for the first time its distance is final — this is the greedy correctness property that requires non-negative weights to hold.
7. Stop early once dst is popped (its distance is now final), or let the heap drain naturally; either way, read the answer off dist[dst], returning -1 if it's still infinity.

The key insight is that a min-heap lets you always process nodes in increasing order of finalized distance, so by the time a node is popped, no cheaper path to it can possibly exist — that greedy guarantee is exactly what non-negative edge weights buy you, and it's what breaks if any edge weight can be negative (Bellman-Ford territory instead).

Reference solution

import heapq
from collections import defaultdict


def min_latency_path(n: int, edges: list[tuple[int, int, int]], src: int, dst: int) -> int:
    graph = defaultdict(list)
    for u, v, latency in edges:
        graph[u].append((v, latency))

    # standard Dijkstra: min-heap of (distance_so_far, node), O((V+E) log V)
    dist = [float("inf")] * n
    dist[src] = 0
    pq = [(0, src)]

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue  # stale heap entry, a shorter path to u was already found
        if u == dst:
            break  # popped the destination with its final (shortest) distance
        for v, latency in graph[u]:
            nd = d + latency
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))

    return dist[dst] if dist[dst] != float("inf") else -1

Key Functions & Tricks

• heapq.heappush / heapq.heappop — min-heap keyed on tentative distance, always exposes the globally closest unfinalized node next.
• collections.defaultdict(list) — builds the adjacency list without pre-declaring every node key.
• Lazy deletion (if d > dist[u]: continue) — cheaper than searching the heap for stale entries to remove; just skip them when popped.
• Edge relaxation (if nd < dist[v]: ...) — the core update step: keep a candidate distance only if it beats the best known so far.
• Early exit on popping dst — once the destination is popped, its distance is final and the rest of the heap can be skipped.

How to Recognize This Pattern