Introduction

Dijkstra Algorithm is one of the most important shortest path algorithms in Graph Theory.

It is used to find:

Shortest Distance from Source Node to Every Other Node

Applicable when:

All Edge Weights are Non-Negative

Example

Input:

n = 5
edges =
0 → 1 (2)
0 → 2 (4)
1 → 2 (1)
1 → 3 (7)
2 → 4 (3)
3 → 4 (1)
source = 0

Output:

[0,2,3,9,6]

Key Observation

Whenever we process a node:

Choose Node having Minimum Distance

This guarantees:

Shortest Path Found

Algorithm

1. Initialize distances2. Distance[source] = 0
3. Push source into min heap
4. Pop minimum distance node
5. Relax neighbors
6. Update distances
7. Repeat

Dry Run

Source:

0

Initial:

[0,∞,∞,∞,∞]

After Processing:

[0,2,3,9,6]

Answer:

Shortest distance from source to every node

Approach : Priority Queue (Min Heap)

Explanation

For every node:

  1. Pick minimum distance node.
  2. Visit neighbors.
  3. Relax edges.
  4. Update distance if shorter path exists.
  5. Push updated distance into heap.

Practice

Complexity Analysis

Using Min HeapTime Complexity: O((V + E) log V)

Space Complexity: O(V + E)

Why This Problem is Important

  • Shortest Path
  • Priority Queue
  • Greedy Algorithm
  • Graph Traversal
  • Foundation for Advanced Graph Problems

Common Beginner Mistakes

  • Using Dijkstra on negative weights
  • Forgetting relaxation step
  • Using max heap instead of min heap
  • Not skipping outdated distances
  • Wrong graph representation

Interview Tip

Always explain:

Pick the node having minimum distance and relax its neighbors.

This is the core idea behind Dijkstra.

Related Questions

  • Network Delay Time
  • Cheapest Flights Within K Stops
  • Path With Minimum Effort
  • Swim in Rising Water

Final Takeaway

Dijkstra Algorithm is the foundation of shortest path problems.

It teaches:

  • Priority Queue
  • Greedy Strategy
  • Graph Traversal
  • Shortest Path Computation

Mastering Dijkstra makes advanced graph and routing problems significantly easier.