Intermediate · Module 17 · Lesson 9
Shortest paths
BFS, Dijkstra, Bellman-Ford, and Floyd-Warshall.
Lesson 103 of 123
1d streakInteractive Visualization
Trace the algorithm state by state
Change the inputs, run an operation, and connect each visible state change to the explanation below.
Interactive algorithm lab
Dijkstra’s Algorithm
Relax weighted edges from the nearest unsettled node
Current
A
Settled
0
Relaxing
—
Reachable
1
Why this step happens
The source has distance 0; every other distance starts at infinity.
Settled nodes always have their final shortest distance.
Dijkstra’s Algorithm: Non-Negative Weighted Shortest Path
Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a directed or undirected graph with non-negative edge weights. Using a Min-Heap (Priority Queue), it greedily expands the frontier by always settling the vertex with the smallest tentative distance in O((V + E) log V) time.
public int[] dijkstra(int n, List<List<int[]>> adj, int src) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
pq.offer(new int[]{src, 0}); // {node, distance}
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int u = curr[0], d = curr[1];
if (d > dist[u]) continue; // Stale distance; ignore
for (int[] edge : adj.get(u)) {
int v = edge[0], weight = edge[1];
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.offer(new int[]{v, dist[v]});
}
}
}
return dist;
}Active Recall Checkpoint
Why does Dijkstra’s algorithm fail when graph edges have negative weights?
Show answer & explanation
Dijkstra operates greedily on the invariant that once a node is popped from the min-heap, its shortest distance is finalized. A negative edge encountered later could lower the distance to an already-settled node, violating the greedy assumption. Bellman-Ford must be used instead.
Use it when
Use Dijkstra for GPS route planning, network packet routing protocols (OSPF), flight cost optimization, and non-negative weighted graphs.
Reconsider when
Reconsider when negative edge weights exist (use Bellman-Ford) or when all edge weights are identical (use BFS in O(V + E) without heap overhead).
Cost Model
Complexity & Trade-offs
When to use it
- Networks, dependencies, connectivity, shortest paths, and grid movement.
- Ordering prerequisite-constrained work.
- Grouping reachable or mutually reachable states.
Common mistakes
- Marking visited too late and enqueuing the same vertex repeatedly.
- Ignoring disconnected components.
- Using an algorithm whose weight assumptions do not match the graph.
Practice prompts
- Reproduce the worked Shortest paths example without looking at the trace.
- Change one input condition and explain whether the Shortest paths invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check