Dijkstra's Algorithm ā Shortest Path Guide
In this tutorial, you'll learn about Dijkstra's Algorithm. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
Dijkstra's algorithm finds the shortest paths from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It uses a priority queue to always expand the closest unvisited vertex.
What You'll Learn
You will learn Dijkstra's algorithm with a priority queue, how to reconstruct shortest paths, handling of edge cases, and why it fails with negative weights.
Why It Matters
Dijkstra's algorithm powers GPS navigation, network routing protocols (OSPF), social network recommendation engines, and any system requiring optimal pathfinding in weighted graphs.
Real-World Use
Durga Antivirus Pro uses Dijkstra's algorithm for network threat propagation analysis. When a threat is detected on one machine, the algorithm finds the shortest infection path through the network topology to identify which systems were likely compromised first.
Dijkstra's Algorithm Flow
graph LR
A((A)) --4--> B((B))
A --2--> C((C))
B --1--> C
B --5--> D((D))
C --8--> D
C --10--> E((E))
D --2--> E
style A fill:#4a90d9,stroke:#333,color:#fff
style B fill:#e67e22,stroke:#333,color:#fff
style C fill:#e67e22,stroke:#333,color:#fff
style D fill:#e67e22,stroke:#333,color:#fff
style E fill:#e67e22,stroke:#333,color:#fff
From A: shortest distances are A(0), C(2), B(3), D(8), E(10).
Implementation with Priority Queue
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)]
previous = {node: None for node in graph}
while pq:
current_dist, current = heapq.heappop(pq)
if current_dist > distances[current]:
continue
for neighbor, weight in graph[current]:
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
previous[neighbor] = current
heapq.heappush(pq, (distance, neighbor))
return distances, previous
def reconstruct_path(previous, start, end):
path = []
curr = end
while curr is not None:
path.append(curr)
curr = previous[curr]
path.reverse()
return path if path[0] == start else []
graph = {
'A': [('B', 4), ('C', 2)],
'B': [('C', 1), ('D', 5)],
'C': [('B', 1), ('D', 8), ('E', 10)],
'D': [('E', 2)],
'E': []
}
distances, previous = dijkstra(graph, 'A')
print("Distances:", distances)
print("Path A -> E:", reconstruct_path(previous, 'A', 'E'))
Expected output:
Distances: {'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10}
Path A -> E: ['A', 'C', 'B', 'D', 'E']
function dijkstra(graph, start) {
const distances = {};
const previous = {};
for (let node in graph) {
distances[node] = Infinity;
previous[node] = null;
}
distances[start] = 0;
const pq = [[0, start]];
while (pq.length) {
pq.sort((a, b) => a[0] - b[0]);
const [currentDist, current] = pq.shift();
if (currentDist > distances[current]) continue;
for (let [neighbor, weight] of graph[current]) {
const distance = currentDist + weight;
if (distance < distances[neighbor]) {
distances[neighbor] = distance;
previous[neighbor] = current;
pq.push([distance, neighbor]);
}
}
}
return { distances, previous };
}
function reconstructPath(previous, start, end) {
const path = [];
let curr = end;
while (curr !== null) {
path.push(curr);
curr = previous[curr];
}
path.reverse();
return path[0] === start ? path : [];
}
const graph = {
'A': [['B', 4], ['C', 2]],
'B': [['C', 1], ['D', 5]],
'C': [['B', 1], ['D', 8], ['E', 10]],
'D': [['E', 2]],
'E': []
};
const { distances, previous } = dijkstra(graph, 'A');
console.log("Distances:", distances);
console.log("Path A -> E:", reconstructPath(previous, 'A', 'E'));
Expected output:
Distances: { A: 0, B: 3, C: 2, D: 8, E: 10 }
Path A -> E: [ 'A', 'C', 'B', 'D', 'E' ]
Efficient Priority Queue Implementation
JavaScript's Array.shift() is O(n). A proper binary heap gives O(log n) per operation:
# Python's heapq already uses a binary heap ā O(log n) push/pop
# This is the recommended implementation
import heapq
def dijkstra_fast(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
current_dist, current = heapq.heappop(pq)
if current_dist > distances[current]:
continue
for neighbor, weight in graph[current]:
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
Finding the Shortest Path to a Target
Early termination when the target is reached:
def dijkstra_to_target(graph, start, end):
distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)]
previous = {node: None for node in graph}
while pq:
current_dist, current = heapq.heappop(pq)
if current == end:
return reconstruct_path(previous, start, end)
if current_dist > distances[current]:
continue
for neighbor, weight in graph[current]:
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
previous[neighbor] = current
heapq.heappush(pq, (distance, neighbor))
return None
Complexity Analysis
| Aspect | Value |
|---|---|
| Time (binary heap) | O((V + E) log V) |
| Time (array) | O(VĀ²) |
| Space | O(V) |
| Edge weights | Must be non-negative |
Dijkstra with Negative Weights
Dijkstra's algorithm fails with negative edges. Once a node is finalized (popped from the PQ), its distance is never updated. A negative edge to a finalized node would reduce its distance, but the algorithm doesn't revisit it.
For negative weights, use Bellman-Ford algorithm (O(VE)).
Common Pitfalls
1. Not Using a Priority Queue
Linear search for the minimum distance node makes the algorithm O(VĀ²). Always use a binary heap for sparse graphs.
2. Forgetting the if current_dist > distances[current] Check
Stale entries in the priority queue must be skipped. Without this check, outdated distances could incorrectly update neighbors.
3. Using Dijkstra on Graphs with Negative Edges
Dijkstra assumes all edge weights are non-negative. Negative edges can cause incorrect results or infinite loops.
4. Not Handling Unreachable Nodes
When a node is unreachable, its distance remains infinity. Code must handle this before path reconstruction.
5. Integer Overflow for Large Distances
Use float('inf') in Python or Infinity in JavaScript. In languages with fixed integers, reserve a sentinel value.
Practice Questions
1. Find the shortest path in a grid with weighted cells using Dijkstra.
def dijkstra_grid(grid):
rows, cols = len(grid), len(grid[0])
distances = [[float('inf')] * cols for _ in range(rows)]
distances[0][0] = grid[0][0]
pq = [(grid[0][0], 0, 0)]
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while pq:
dist, r, c = heapq.heappop(pq)
if dist > distances[r][c]:
continue
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
new_dist = dist + grid[nr][nc]
if new_dist < distances[nr][nc]:
distances[nr][nc] = new_dist
heapq.heappush(pq, (new_dist, nr, nc))
return distances[rows - 1][cols - 1]
2. Find the cheapest flight with at most k stops.
3. Network delay time: find the time for a signal to reach all nodes in a network.
4. Challenge: Implement the A* algorithm, which extends Dijkstra with a heuristic to guide search toward the goal. Compare A* with Dijkstra on a grid.
5. Real-world task: Doda Browser's download manager calculates optimal routing for downloading large files from multiple mirrors. Write a function that models mirrors as graph nodes with latency weights and uses Dijkstra to find the fastest download path.
What's Next
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro