Dijkstra's Algorithm

Finds shortest paths from source to all vertices

Algorithm Code

Time: O(V² + E) | Space: O(V)

1function dijkstra(graph, start) {
2  dist = {}
3  visited = {}
4  previous = {}
5  
6  // Initialize distances
7  for each vertex v in graph:
8    dist[v] = Infinity
9    previous[v] = null
10  dist[start] = 0
11  
12  while unvisited vertices exist:
13    u = vertex with minimum distance
14    visited[u] = true
15    
16    for each neighbor v of u:
17      alt = dist[u] + weight(u, v)
18      if alt < dist[v]:
19        dist[v] = alt
20        previous[v] = u
21  
22  return dist, previous
23}

Algorithm Steps

Step 1 of 11

1

Initialize

Set all distances to infinity except start node (A) = 0

2

Select A (dist: 0)

Visit node A with minimum distance. Update neighbors B and C.

3

Update distances from A

A→B: 0+4=4, A→C: 0+2=2. Mark A as visited.

4

Select C (dist: 2)

Visit node C with minimum unvisited distance.

5

Update distances from C

C→B: 2+1=3 < 4, update B. C→D: 2+7=9.

6

Select B (dist: 3)

Visit node B with minimum unvisited distance.

7

Update distances from B

B→D: 3+3=6 < 9, update D. B→E: 3+2=5.

8

Select E (dist: 5)

Visit node E with minimum unvisited distance.

9

Update distances from E

E→D: 5+1=6, no improvement for D.

10

Select D (dist: 6)

Visit final node D. All nodes visited!

11

Algorithm Complete

Shortest paths from A: B(3), C(2), D(6), E(5)

Dijkstra's Algorithm

Finding shortest paths from A

4213271A0B∞C∞D∞E∞

Current Distances from A:

A
0
B
∞
C
∞
D
∞
E
∞
Unvisited
Current Min
Visited
Active Edge
Step 0 of 100%
0.25x4x