Shortest Path

Dijkstra's Algorithm

Find shortest paths in weighted graphs with non-negative edge weights

What is Dijkstra's Algorithm?

Dijkstra's algorithm finds the shortest paths from a source vertex to all other vertices in a weighted graph with non-negative edge weights.

Key Features:

  • Works with weighted graphs
  • Guarantees optimal solution
  • Uses priority queue (min-heap)
  • Greedy algorithm approach

Complexity Analysis

Time: O((V + E) log V)
Space: O(V)

With binary heap implementation

How It Works

  1. Initialize: Set distance to source as 0, all others as infinity
  2. Priority Queue: Add all vertices to min-heap by distance
  3. Extract Minimum: Remove vertex with smallest distance
  4. Relax Edges: Update distances to neighbors if shorter path found
  5. Repeat: Continue until all vertices processed

Real-World Applications

🗺️ GPS Navigation

Finding shortest routes in road networks

🌐 Network Routing

Internet packet routing protocols

✈️ Flight Planning

Optimal flight paths and scheduling

🎮 Game AI

Pathfinding for NPCs and game mechanics

Worked Example

Consider a graph with vertices A, B, C, D and weighted edges:

Edges: A→B(4), A→C(2), B→C(1), B→D(5), C→D(8), C→B(3)

Source: A

Step 1: dist[A]=0, dist[B]=∞, dist[C]=∞, dist[D]=∞

Step 2: Process A: dist[B]=4, dist[C]=2

Step 3: Process C: dist[B]=min(4,2+3)=4, dist[D]=2+8=10

Step 4: Process B: dist[D]=min(10,4+5)=9

Result: A→A(0), A→C(2), A→B(4), A→D(9)

Important Notes

✅ Works with non-negative weights

All edge weights must be ≥ 0 for correctness

❌ Cannot handle negative weights

Use Bellman-Ford algorithm for graphs with negative weights

Try Dijkstra Visualizer →