8 views
# Dijkstra Shortest Path (Practice 4147): Scan Interviewers love dijkstra shortest path because it checks whether you can state the invariant before coding. Here is a compact rehearsal note. ## Approach Min-heap of (dist, node); relax neighbors. ```python import heapq def dijkstra(n, edges, src): g = [[] for _ in range(n)] for u, v, w in edges: g[u].append((v, w)) dist = [10**18]*n; dist[src] = 0 pq = [(0, src)] while pq: d, u = heapq.heappop(pq) if d != dist[u]: continue for v, w in g[u]: if d + w < dist[v]: dist[v] = d + w; heapq.heappush(pq, (dist[v], v)) return dist ``` ## Complexity Linear in the dominant input size for the scan; heap/tree variants add a log factor. ## Interview pitfalls State the invariant out loud, name the complexity, then code. Skipping the invariant is the usual fail mode. ## Practicing out loud Narrate the approach, complexity and one edge case in under a minute. Disclosure: I work on Linkjob AI, a real-time interview assistant. If you want live practice help, see [real-time AI interview assistant for live interviews](https://www.linkjob.ai/).