Dijkstra’s Shortest Paths
The algorithm every routing table, map app and network protocol leans on: single-source shortest paths on a graph with non-negative weights. Greedily settle the closest unsettled node, relax its edges, repeat. Return the distance to every node. Solve it in Python or TypeScript, with hidden tests.
The problem
You are given n nodes (0…n-1), a list of directed weighted edges [u, v, w] with w ≥ 0, and a source src. Return a list dist where dist[i] is the length of the shortest path from src to node i, or -1 if i is unreachable.
n = 5, edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5]], src = 0[0, 3, 1, 4, -1]- All edge weights are non-negative — this is what lets the greedy "settle the closest node" step be correct.
- Edges are directed; there may be several edges into a node.
- Unreachable nodes return
-1. The source’s own distance is 0.
Your turn — write it
Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.
Implement dijkstra(n, edges, src): keep tentative distances (∞ except the source at 0). Repeatedly pick the unsettled node with the smallest distance, settle it, and relax each outgoing edge (dist[v] = min(dist[v], dist[u] + w)). Return distances, using -1 for anything still ∞.
- Build an adjacency list from the edges. Start with
dist[src] = 0and all others "infinity". - On each of the n rounds, choose the unsettled node with the minimum tentative distance (a priority queue makes this fast; a linear scan is fine for small graphs).
- Settling a node with non-negative weights means its distance is final — relax its outgoing edges to possibly improve neighbours.
- If the smallest remaining distance is infinity, the rest are unreachable — stop and mark them
-1.
Explore the topic
See this challenge alongside everything else on the same subject — handbooks, system designs, algorithms and tools, in one place.