Dijkstra's Algorithm - Shortest Path
Medium
💭 Introduction
You’re given a weighted graph and a starting vertex. Your task is to find the shortest path from the starting vertex to all other vertices in the graph.
Dijkstra’s Algorithm is a greedy algorithm that efficiently solves the single-source shortest path problem for graphs with non-negative edge weights.
Named after Dutch computer scientist Edsger W. Dijkstra, this algorithm is fundamental in computer science and has countless real-world applications from GPS navigation to network routing.
🧩 Problem Statement
Single-Source Shortest Path Problem
Given a weighted graph G = (V, E) with non-negative edge weights and a source vertex s, find the shortest path from s to every other vertex in the graph.
🔍 Example 1:
Graph:
(0)---1---(1)
| \ |
4 2 3
| \ |
(3)---5---(2)
Source: 0
Output:
Vertex 0: Distance = 0
Vertex 1: Distance = 1
Vertex 2: Distance = 3
Vertex 3: Distance = 4
Explanation:
- 0 → 1: Direct edge with weight 1
- 0 → 2: Path 0 → 1 → 2 with total weight 1 + 2 = 3
- 0 → 3: Direct edge with weight 4
🔍 Example 2:
Graph:
(0)---4---(1)---8---(2)
| | |
8 11 2
| | |
(7)---7---(6)---6---(3)
| \ | / |
1 7 2 10 4
| \ | / |
(8)---6---(5)---14--(4)
Source: 0
Shortest paths from 0:
0 → 1: 4
0 → 2: 12
0 → 3: 19
0 → 4: 21
0 → 5: 11
0 → 6: 9
0 → 7: 8
0 → 8: 9
🧠 Step 1: Understanding the Algorithm
Core Idea: Dijkstra’s algorithm maintains a set of vertices whose shortest distance from the source is already known. It repeatedly selects the vertex with the minimum distance from the unvisited set and updates distances to its neighbors.
Key Components:
- Distance Array:
dist[v]= shortest known distance from source to vertex v - Priority Queue: Min-heap to efficiently get vertex with minimum distance
- Visited Set: Track which vertices have been processed
Algorithm Steps:
- Initialize all distances to infinity, except source (distance = 0)
- Add source to priority queue
- While priority queue is not empty:
- Extract vertex with minimum distance
- For each neighbor of this vertex:
- Calculate new distance through current vertex
- If new distance is shorter, update it
- Return distance array
🤔 Step 2: The Naive Approach (Without Priority Queue)
def dijkstra_naive(graph, source, n):
"""
graph: adjacency list {vertex: [(neighbor, weight), ...]}
source: starting vertex
n: number of vertices
"""
# Initialize distances
dist = [float('inf')] * n
dist[source] = 0
visited = [False] * n
for _ in range(n):
# Find unvisited vertex with minimum distance
min_dist = float('inf')
u = -1
for v in range(n):
if not visited[v] and dist[v] < min_dist:
min_dist = dist[v]
u = v
if u == -1: # No more reachable vertices
break
visited[u] = True
# Update distances to neighbors
if u in graph:
for neighbor, weight in graph[u]:
if not visited[neighbor]:
new_dist = dist[u] + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
return dist
Problem: Finding minimum distance vertex takes O(V) time each iteration!
⏱️ Time Complexity: $O(V^2)$
📦 Space Complexity: $O(V)$
🚀 Step 3: Optimized with Priority Queue (Min-Heap)
Using a priority queue (min-heap) to efficiently get the vertex with minimum distance:
import heapq
from collections import defaultdict
class Solution:
def dijkstra(self, graph, source, n):
"""
graph: adjacency list {vertex: [(neighbor, weight), ...]}
source: starting vertex
n: number of vertices
Returns: list of shortest distances from source
"""
# Initialize distances
dist = [float('inf')] * n
dist[source] = 0
# Priority queue: (distance, vertex)
pq = [(0, source)]
visited = set()
while pq:
current_dist, u = heapq.heappop(pq)
# Skip if already visited
if u in visited:
continue
visited.add(u)
# Update distances to neighbors
if u in graph:
for neighbor, weight in graph[u]:
if neighbor not in visited:
new_dist = current_dist + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
return dist
⏱️ Time Complexity: $O((V + E) \log V)$
📦 Space Complexity: $O(V)$
⚙️ Step 4: With Path Reconstruction
To get the actual shortest paths, not just distances:
import heapq
from collections import defaultdict
class Solution:
def dijkstra_with_path(self, graph, source, n):
"""
Returns both distances and the actual shortest paths
"""
dist = [float('inf')] * n
dist[source] = 0
parent = [-1] * n # Track path
pq = [(0, source)]
visited = set()
while pq:
current_dist, u = heapq.heappop(pq)
if u in visited:
continue
visited.add(u)
if u in graph:
for neighbor, weight in graph[u]:
if neighbor not in visited:
new_dist = current_dist + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
parent[neighbor] = u
heapq.heappush(pq, (new_dist, neighbor))
return dist, parent
def get_path(self, parent, source, target):
"""Reconstruct path from source to target"""
if parent[target] == -1 and target != source:
return [] # No path exists
path = []
current = target
while current != -1:
path.append(current)
current = parent[current]
return path[::-1] # Reverse to get source → target
🧪 Step 5: Complete Example with Trace
Let’s trace through Example 1:
Graph:
(0)---1---(1)
| \ |
4 2 3
| \ |
(3)---5---(2)
Adjacency List:
0: [(1, 1), (2, 2), (3, 4)]
1: [(0, 1), (2, 3)]
2: [(0, 2), (1, 3), (3, 5)]
3: [(0, 4), (2, 5)]
Step-by-step execution:
| Step | PQ (dist, vertex) | Current | Visited | dist[0] | dist[1] | dist[2] | dist[3] | Action |
|---|---|---|---|---|---|---|---|---|
| 0 | [(0, 0)] | - | {} | 0 | ∞ | ∞ | ∞ | Initialize |
| 1 | [(1, 1), (2, 2), (4, 3)] | 0 | {0} | 0 | 1 | 2 | 4 | Process 0 |
| 2 | [(2, 2), (4, 1), (4, 3)] | 1 | {0,1} | 0 | 1 | 2 | 4 | Process 1, update 2 |
| 3 | [(4, 1), (4, 3)] | 2 | {0,1,2} | 0 | 1 | 2 | 4 | Process 2 |
| 4 | [(4, 3)] | 1 | {0,1,2} | 0 | 1 | 2 | 4 | Skip (visited) |
| 5 | [] | 3 | {0,1,2,3} | 0 | 1 | 2 | 4 | Process 3 |
Final Result:
- Distance to 0: 0
- Distance to 1: 1
- Distance to 2: 2
- Distance to 3: 4
🎯 Key Insights
-
Greedy Choice: Always process the vertex with minimum distance next
-
Non-negative weights: Algorithm fails with negative weights (use Bellman-Ford instead)
-
Priority Queue: Essential for efficiency — reduces from O(V²) to O((V+E) log V)
-
Relaxation: Core operation is “relaxing” edges to find shorter paths
-
Optimal Substructure: Shortest path to v through u uses shortest path to u
📊 Complexity Analysis
| Implementation | Time Complexity | Space Complexity | Best For |
|---|---|---|---|
| Array (Naive) | $O(V^2)$ | $O(V)$ | Dense graphs |
| Binary Heap | $O((V + E) \log V)$ | $O(V)$ | Sparse graphs |
| Fibonacci Heap | $O(E + V \log V)$ | $O(V)$ | Theoretical optimum |
When to use which:
- Dense graphs (E ≈ V²): Array implementation is simpler and comparable
- Sparse graphs (E « V²): Binary heap is much faster
- Practice: Binary heap is the standard choice
🌟 Edge Cases to Consider
- Disconnected graph: Some vertices unreachable (distance = ∞)
- Single vertex: Source to itself has distance 0
- No edges: Only source has distance 0, rest are ∞
- Negative weights: Algorithm doesn’t work! Use Bellman-Ford
- Self-loops: Can be ignored (never improve shortest path)
- Multiple edges: Keep only the one with minimum weight
💡 Common Mistakes
- Forgetting to check visited: May process same vertex multiple times
- Using wrong data structure: List instead of heap makes it O(V²)
- Not handling disconnected components: Check for unreachable vertices
- Negative weights: Dijkstra doesn’t work with negative weights
- Wrong priority queue order: Should be (distance, vertex), not (vertex, distance)
🔍 LeetCode Problems Using Dijkstra
Easy/Medium:
- Network Delay Time (LC 743) - Direct application ⭐
- Path with Maximum Probability (LC 1514) - Modified Dijkstra
- Cheapest Flights Within K Stops (LC 787) - With constraints
- Minimum Cost to Make at Least One Valid Path (LC 1368)
Hard:
- Shortest Path Visiting All Nodes (LC 847)
- Minimum Cost to Reach Destination in Time (LC 1928)
🧮 Step 6: Network Delay Time (LeetCode 743)
📚 Full Solution Guide
For a complete, detailed walkthrough of this problem with multiple approaches, step-by-step traces, edge cases, and interview tips, check out our dedicated post: Network Delay Time - Complete Guide
Problem: You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.
We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.
import heapq
from collections import defaultdict
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
# Build adjacency list
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
# Dijkstra's algorithm
dist = {i: float('inf') for i in range(1, n + 1)}
dist[k] = 0
pq = [(0, k)] # (distance, node)
while pq:
current_dist, u = heapq.heappop(pq)
if current_dist > dist[u]:
continue
for v, weight in graph[u]:
new_dist = current_dist + weight
if new_dist < dist[v]:
dist[v] = new_dist
heapq.heappush(pq, (new_dist, v))
# Find maximum distance
max_dist = max(dist.values())
return max_dist if max_dist != float('inf') else -1
🎯 Real-World Applications
- GPS Navigation: Finding shortest routes in road networks
- Network Routing: Optimal packet routing in computer networks
- Flight Planning: Cheapest flight paths
- Game Development: AI pathfinding
- Social Networks: Degrees of separation
- Telecommunications: Optimal signal routing
🔄 Comparison with Other Algorithms
| Algorithm | Negative Weights? | Time Complexity | Use Case |
|---|---|---|---|
| Dijkstra | ❌ No | $O((V+E) \log V)$ | Single-source, non-negative |
| Bellman-Ford | ✅ Yes | $O(VE)$ | Single-source, any weights |
| Floyd-Warshall | ✅ Yes | $O(V^3)$ | All-pairs shortest path |
| BFS | Only unweighted | $O(V+E)$ | Unweighted graphs |
💡 Related Problems
- Bellman-Ford Algorithm - Handles negative weights
- Floyd-Warshall Algorithm - All-pairs shortest path
- A* Algorithm - Heuristic-based pathfinding
- Prim’s Algorithm - Minimum Spanning Tree (similar structure)
🏆 Why This Algorithm Matters
- Fundamental algorithm: Core concept in graph theory
- Interview favorite: Extremely common in technical interviews
- Practical applications: Used in countless real-world systems
- Foundation for variants: Basis for many other algorithms
- Greedy paradigm: Classic example of greedy algorithm design
🎓 Key Takeaways
- Greedy approach: Always choose vertex with minimum distance
- Priority queue is essential: Makes algorithm efficient
- Non-negative weights only: Critical limitation to remember
- Relaxation technique: Core operation for updating distances
- Path reconstruction: Use parent array to track actual paths
📝 Interview Tips
- Clarify graph representation: Adjacency list vs matrix
- Ask about edge weights: Confirm they’re non-negative
- Discuss complexity: Explain why priority queue is needed
- Handle edge cases: Disconnected graphs, single vertex
- Code cleanly: Use clear variable names, add comments
- Test thoroughly: Walk through a small example
🔧 Implementation Variations
Using Dictionary for Sparse Graphs:
def dijkstra_dict(graph, source):
dist = {source: 0}
pq = [(0, source)]
while pq:
current_dist, u = heapq.heappop(pq)
if current_dist > dist.get(u, float('inf')):
continue
for v, weight in graph.get(u, []):
new_dist = current_dist + weight
if new_dist < dist.get(v, float('inf')):
dist[v] = new_dist
heapq.heappush(pq, (new_dist, v))
return dist
Finding Single Target:
```python
def dijkstra_single_target(graph, source, target, n): “"”Early termination when target is reached””” dist = [float(‘inf’)] * n dist[source] = 0 pq = [(0, source)]
while pq:
current_dist, u = heapq.heappop(pq)
if u == target:
return current_dist
if current_dist > dist[u]:
continue
for v, weight in graph.get(u, []):
new_dist = current_dist + weight
if new_dist < dist[v]:
dist[v] = new_dist
heapq.heappush(pq, (new_dist, v))
return -1 # Target not reachable