Dijkstra's Algorithm: Shortest Path in Weighted Graphs
Every time you ask Google Maps for directions, request a route in a video game, or send a packet across the internet, a shortest path algorithm runs behind the scenes. These systems model their...
Key Insights
- Dijkstra’s algorithm finds the shortest path in weighted graphs by greedily selecting the unvisited node with the smallest known distance, achieving O((V + E) log V) time complexity with a priority queue implementation.
- The algorithm only works correctly with non-negative edge weights; negative weights require Bellman-Ford, while negative cycles make shortest paths undefined.
- Path reconstruction requires storing parent pointers during relaxation, allowing you to trace back from the destination to the source after the algorithm completes.
The Shortest Path Problem
Every time you ask Google Maps for directions, request a route in a video game, or send a packet across the internet, a shortest path algorithm runs behind the scenes. These systems model their domains as weighted graphs—intersections as nodes, roads as edges, travel time as weights—and need to find optimal routes quickly.
For unweighted graphs, BFS works perfectly. It explores nodes level by level, guaranteeing the first time you reach a node is via the shortest path (measured in edge count). But when edges have different weights, BFS fails spectacularly. A path with three low-weight edges might be shorter than a direct high-weight edge.
Dijkstra’s algorithm, published by Edsger Dijkstra in 1959, solves this problem elegantly. It’s the foundation for most real-world routing systems and a prerequisite for understanding more advanced algorithms like A*.
How Dijkstra’s Algorithm Works
The core insight is deceptively simple: if you always process the unvisited node with the smallest known distance, you can guarantee that node’s distance is final. This greedy approach works because all edge weights are non-negative—there’s no way a longer path could become shorter by adding more edges.
The algorithm maintains a distance estimate for each node, initially set to infinity except for the source (which is zero). It then repeatedly selects the unvisited node with minimum distance, marks it as visited, and “relaxes” all its outgoing edges.
Relaxation is the key operation. For each neighbor of the current node, you check: is the path through the current node shorter than the best known path to that neighbor? If so, update the neighbor’s distance.
Here’s the conceptual flow:
DIJKSTRA(graph, source):
distance[source] = 0
distance[all other nodes] = infinity
visited = empty set
while unvisited nodes remain:
current = unvisited node with minimum distance
mark current as visited
for each neighbor of current:
new_distance = distance[current] + weight(current, neighbor)
if new_distance < distance[neighbor]:
distance[neighbor] = new_distance
return distance
Consider a simple graph with nodes A, B, C, D where A connects to B (weight 1) and C (weight 4), B connects to C (weight 2) and D (weight 6), and C connects to D (weight 3). Starting from A:
- Initialize: A=0, B=∞, C=∞, D=∞
- Process A (distance 0): Update B=1, C=4
- Process B (distance 1): Update C=min(4, 1+2)=3, D=7
- Process C (distance 3): Update D=min(7, 3+3)=6
- Process D (distance 6): No updates needed
The shortest path from A to D is 6, going A→B→C→D.
Implementation with Priority Queue
The naive implementation scans all nodes to find the minimum distance, giving O(V²) time complexity. For sparse graphs (most real-world networks), this is unacceptable. A priority queue reduces this to O((V + E) log V).
import heapq
from collections import defaultdict
from typing import Dict, List, Tuple
def dijkstra(
graph: Dict[str, List[Tuple[str, int]]],
source: str
) -> Dict[str, int]:
"""
Find shortest distances from source to all reachable nodes.
Args:
graph: Adjacency list where graph[u] = [(v, weight), ...]
source: Starting node
Returns:
Dictionary mapping each node to its shortest distance from source
"""
# Initialize distances
distances: Dict[str, int] = defaultdict(lambda: float('inf'))
distances[source] = 0
# Priority queue: (distance, node)
# Python's heapq is a min-heap, perfect for Dijkstra
pq: List[Tuple[int, str]] = [(0, source)]
# Track processed nodes
visited: set = set()
while pq:
current_dist, current_node = heapq.heappop(pq)
# Skip if already processed
# This handles duplicate entries in the priority queue
if current_node in visited:
continue
visited.add(current_node)
# Relaxation step
for neighbor, weight in graph[current_node]:
if neighbor in visited:
continue
new_distance = current_dist + weight
if new_distance < distances[neighbor]:
distances[neighbor] = new_distance
heapq.heappush(pq, (new_distance, neighbor))
return dict(distances)
# Example usage
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('C', 2), ('D', 6)],
'C': [('D', 3)],
'D': []
}
distances = dijkstra(graph, 'A')
print(distances) # {'A': 0, 'B': 1, 'C': 3, 'D': 6}
A few implementation notes worth highlighting:
The duplicate check (if current_node in visited) is essential. When we find a shorter path to a node, we push a new entry to the priority queue rather than updating the existing one (which heapq doesn’t support efficiently). This means the queue may contain multiple entries for the same node with different distances.
Using defaultdict(lambda: float('inf')) simplifies initialization. Any node we haven’t explicitly set starts with infinite distance.
Time and Space Complexity Analysis
With a binary heap priority queue, each node is processed once (O(V) operations), and each edge triggers at most one push to the heap (O(E) operations). Each heap operation costs O(log V), giving us O((V + E) log V) total.
For dense graphs where E approaches V², this becomes O(V² log V)—actually worse than the naive O(V²) array-based approach. In practice, most graphs are sparse, making the heap version faster.
A Fibonacci heap can theoretically achieve O(V log V + E), but the constant factors make it slower for typical graph sizes. Stick with binary heaps unless you’re working with truly massive graphs.
Space complexity is O(V + E) for the adjacency list representation plus O(V) for the distance array and visited set. The priority queue can grow to O(E) in the worst case due to duplicate entries, though you can bound this to O(V) with a more complex implementation using decrease-key operations.
For adjacency matrices, you trade O(V²) space for O(1) edge weight lookups. This only makes sense for dense graphs or when you need to frequently check whether edges exist.
Limitations and Edge Cases
Dijkstra’s algorithm has one critical limitation: it fails with negative edge weights. The greedy assumption—that processing a node finalizes its distance—breaks when a longer path could become shorter by traversing a negative edge.
def dijkstra_safe(
graph: Dict[str, List[Tuple[str, int]]],
source: str
) -> Dict[str, int]:
"""
Dijkstra with input validation.
Raises:
ValueError: If graph contains negative edge weights
KeyError: If source node doesn't exist in graph
"""
# Validate source exists
if source not in graph:
raise KeyError(f"Source node '{source}' not found in graph")
# Check for negative weights
for node, edges in graph.items():
for neighbor, weight in edges:
if weight < 0:
raise ValueError(
f"Negative edge weight {weight} found from "
f"'{node}' to '{neighbor}'. Use Bellman-Ford instead."
)
# Proceed with standard Dijkstra
return dijkstra(graph, source)
def get_distance(
distances: Dict[str, int],
target: str
) -> int | None:
"""
Safely retrieve distance to target node.
Returns None if target is unreachable (disconnected graph).
"""
dist = distances.get(target, float('inf'))
return None if dist == float('inf') else dist
For disconnected graphs, unreachable nodes simply retain their infinite distance. This isn’t an error—it’s useful information. Your calling code should handle this case appropriately.
Practical Applications and Variations
Knowing the shortest distance is often not enough—you need the actual path. Track parent pointers during relaxation to enable path reconstruction:
from typing import Optional
def dijkstra_with_path(
graph: Dict[str, List[Tuple[str, int]]],
source: str,
target: str
) -> Tuple[Optional[int], List[str]]:
"""
Find shortest path and distance from source to target.
Returns:
Tuple of (distance, path) where path is list of nodes.
Returns (None, []) if target is unreachable.
"""
distances: Dict[str, int] = defaultdict(lambda: float('inf'))
distances[source] = 0
# Track the previous node in the shortest path
parents: Dict[str, Optional[str]] = {source: None}
pq: List[Tuple[int, str]] = [(0, source)]
visited: set = set()
while pq:
current_dist, current_node = heapq.heappop(pq)
if current_node in visited:
continue
visited.add(current_node)
# Early termination if we've reached the target
if current_node == target:
break
for neighbor, weight in graph[current_node]:
if neighbor in visited:
continue
new_distance = current_dist + weight
if new_distance < distances[neighbor]:
distances[neighbor] = new_distance
parents[neighbor] = current_node
heapq.heappush(pq, (new_distance, neighbor))
# Reconstruct path
if target not in parents:
return None, []
path = []
current = target
while current is not None:
path.append(current)
current = parents[current]
path.reverse()
return distances[target], path
# Example
distance, path = dijkstra_with_path(graph, 'A', 'D')
print(f"Distance: {distance}, Path: {' -> '.join(path)}")
# Distance: 6, Path: A -> B -> C -> D
The A* algorithm extends Dijkstra by adding a heuristic that estimates remaining distance to the goal. Instead of selecting the node with minimum distance from source, A* selects the node with minimum distance + heuristic(node, goal). With an admissible heuristic (one that never overestimates), A* finds optimal paths while exploring fewer nodes.
When to Use Dijkstra’s
Choose your shortest path algorithm based on your constraints:
Dijkstra’s: Single-source shortest paths with non-negative weights. The go-to choice for most applications including GPS, network routing, and game pathfinding.
Bellman-Ford: Single-source with possible negative weights. Slower at O(VE) but handles negative edges and detects negative cycles.
Floyd-Warshall: All-pairs shortest paths. O(V³) time but gives you distances between every pair of nodes in one pass.
A*: Single-source to single-target with a good heuristic. Faster than Dijkstra when you only need one specific path and can estimate distances.
Dijkstra’s algorithm remains one of the most practical algorithms in computer science. Master it, understand its limitations, and you’ll have a powerful tool for solving real-world routing problems.