Dijkstra's Algorithm

Finding Shortest Paths in Weighted Graphs

What is Dijkstra's Algorithm?

  • Finds shortest path from source node to all other nodes
  • Works on graphs with non-negative edge weights
  • Uses greedy approach with relaxation
  • Time Complexity: O((V+E) log V) with priority queue

Key Concepts

Distance Array

Stores shortest known distance from source to each node

Priority Queue

Stores unvisited nodes, always picks node with minimum distance

Relaxation

Updating distance if shorter path found through current node

Visited Set

Tracks processed nodes to avoid rechecking

Algorithm Steps

  1. Initialize: Set source distance to 0, all others to infinity
  2. Add source to priority queue
  3. While priority queue not empty:
    • Extract node with minimum distance
    • Mark as visited
    • For each unvisited neighbor:
      • Calculate distance through current node
      • If shorter than known distance, update it
  4. Return distance array with shortest paths

Pseudocode

function Dijkstra(Graph, source):
    for each vertex v in Graph:
        dist[v] ← INFINITY
        prev[v] ← UNDEFINED
    dist[source] ← 0
    
    Q ← priority queue with all vertices
    
    while Q is not empty:
        u ← vertex in Q with min dist[u]
        remove u from Q
        
        for each neighbor v of u:
            alt ← dist[u] + weight(u, v)
            if alt < dist[v]:
                dist[v] ← alt
                prev[v] ← u
    
    return dist, prev

Step-by-Step Example 1

Min Priority Queue

Step 0 of 6
Initialize: Source node A has distance 0, all others have distance infinity

Distance Table

Node Distance Previous

Step-by-Step Example 2

Min Priority Queue

Step 0 of 5
Initialize: Source node S has distance 0, all others have distance infinity

Distance Table

Node Distance Previous

Time & Space Complexity

Implementation Time Complexity Space Complexity
Array O(V²) O(V)
Binary Heap O((V+E) log V) O(V)
Fibonacci Heap O(E + V log V) O(V)

Note: Most common is binary heap implementation

Key Takeaways

  • Dijkstra finds shortest paths from single source to all nodes
  • Requires non-negative edge weights
  • Uses greedy approach: always picks closest unvisited node
  • Relaxation updates distances when shorter path found
  • Efficient with priority queue: O((V+E) log V)
  • Cannot handle negative weights (use Bellman-Ford instead)