Find the cheapest route in a graph where edges have different costs, by always expanding the closest unvisited node first.
Used for
B = 4, C = 1
1 + 2 = 3 < 4
3 + 1 = 4
Why did B's cost change from 4 to 3?
Not quite. Going A→C→B costs 1 + 2 = 3, which beats the direct road A→B at 4.
Step 1 of 6
Goal: the cheapest route from A to every place when roads have different costs: A→B 4, A→C 1, C→B 2, B→D 1. Keep a table of the best known cost to each place: 0 for A, unknown for the rest.
Step 2 of 6
Always finish the closest unfinished place first: A (cost 0). Try its roads: B costs 0 + 4 = 4 and C costs 0 + 1 = 1.
Step 3 of 6
The closest unfinished place is now C (1). The road C→B gives B a cost of 1 + 2 = 3, cheaper than 4, so update B.
Step 4 of 6
Closest unfinished: B (3). The road B→D gives D a cost of 3 + 1 = 4.
Step 5 of 6
The cheapest A to D is 4, via A, C, B, D. Finishing the closest place first guarantees no later road can beat it, as long as no cost is negative. A priority queue finds the closest place quickly. This is Dijkstra's algorithm.
Step 6 of 6
Your turn.
Prim's AlgorithmDijkstra's AlgorithmBellman–Ford AlgorithmFloyd–Warshall Algorithm
// Dijkstra: expand the closest unvisited node using a priority queue.// See the Dijkstra topic for the full implementation on top of PriorityQueue.