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

Code Implementation

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

Ready to Understand Dijkstra Visually?

Don't just read about it. Use our interactive graph visualizer to build custom weighted graphs, run Dijkstra's algorithm step-by-step, and watch the priority queue and distance table update in real-time.

Launch Dijkstra Visualizer →