Dijkstra's Shortest Path

Dijkstra's Shortest PathO(E + V log V)

Best on a larger screen

AlgoViz's interactive walkthrough is built for a tablet or larger. Rotate your device or open it on a wider screen to explore the visualization.

Loading walkthrough.

SPEED

WalkthroughSTEP 0 / 0

Loading walkthrough.

Keyboard shortcuts

1function Dijkstra(Graph, source):

2 dist[source] = 0

3 create priority queue Q

4 while Q is not empty:

5 u = Q.extract_min()

6 for each neighbor v of u:

7 alt = dist[u] + length(u, v)

8 if alt < dist[v]:

9 dist[v] = alt

Edit the input and run it through the same engine that drives the walkthrough.

source: A
target: G
A B 4
A C 2
B D 5
B E 2
C F 3
D E 1
E G 3
F G 6

Ask about this step or this algorithm.

Try: "Why a heap here?" or "What does this counter track?"