BFS and DFS are the foundational graph traversals, but they ignore edge weights and graph structure. Real-world shortest path problems — GPS navigation, network routing, game pathfinding — require algorithms that exploit heuristics, bidirectional search, and specialized data structures to handle graphs with billions of edges.
Dijkstra's Algorithm: The Foundation
Dijkstra's algorithm finds shortest paths from a source to all vertices using a priority queue:
import heapq
def dijkstra(graph: dict, source: str) -> dict:
"""Dijkstra: O((V + E) log V) with binary heap."""
dist = {v: float('inf') for v in graph}
dist[source] = 0
pq = [(0, source)]
visited = set()
while pq:
d, u = heapq.heappop(pq)
if u in visited:
continue
visited.add(u)
for v, weight in graph[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
heapq.heappush(pq, (dist[v], v))
return distThe priority queue is the bottleneck. Binary heap gives O(log V) per extract-min and decrease-key. Fibonacci heap improves decrease-key to O(1) amortized, but the constant factors make it slower in practice.
A* Search: Exploiting Heuristics
A* adds a heuristic function h(n) that estimates the distance from n to the goal:
import heapq
def a_star(graph, positions, source, goal):
"""A* with Euclidean heuristic for geometric graphs."""
def h(node):
# Euclidean distance to goal
dx = positions[node][0] - positions[goal][0]
dy = positions[node][1] - positions[goal][1]
return (dx*dx + dy*dy) ** 0.5
g_score = {source: 0}
f_score = {source: h(source)}
open_set = [(f_score[source], source)]
came_from = {}
while open_set:
_, current = heapq.heappop(open_set)
if current == goal:
return reconstruct_path(came_from, current)
for neighbor, weight in graph[current]:
tentative_g = g_score[current] + weight
if tentative_g < g_score.get(neighbor, float('inf')):
came_from[neighbor] = current
g_score[neighbor] = tentative_g
f_score[neighbor] = tentative_g + h(neighbor)
heapq.heappush(open_set, (f_score[neighbor], neighbor))
return None # no path foundThe heuristic must be admissible (never overestimates) for A* to guarantee optimality. With an admissible heuristic, A* expands fewer nodes than Dijkstra — often exponentially fewer.
# A* node expansion comparison (grid maze, 1000x1000):
# BFS: expands ~1,000,000 nodes (explores everything)
# Dijkstra: expands ~800,000 nodes (weight-aware)
# A* (Manhattan): expands ~15,000 nodes (10-100× fewer)
# A* (Euclidean): expands ~8,000 nodesBidirectional Search
Instead of searching from source to goal, search from both ends simultaneously:
def bidirectional_bfs(graph, source, goal):
"""Bidirectional BFS: O(b^(d/2)) instead of O(b^d)."""
if source == goal:
return [source]
front_visited = {source: None}
back_visited = {goal: None}
front_queue = [source]
back_queue = [goal]
while front_queue and back_queue:
# Expand smaller frontier first
if len(front_queue) <= len(back_queue):
meeting = expand_layer(graph, front_queue, front_visited)
else:
meeting = expand_layer(graph, back_queue, back_visited)
if meeting:
return reconstruct_bidirectional(
front_visited, back_visited, meeting)
return None
def expand_layer(graph, queue, visited):
next_queue = []
for node in queue:
for neighbor in graph[node]:
if neighbor in visited:
return neighbor # meeting point found
visited[neighbor] = node
next_queue.append(neighbor)
queue[:] = next_queue
return NoneContraction Hierarchies
For road networks, preprocessing is worth it. Contraction hierarchies (CH) add "shortcut" edges for important vertices, enabling queries in microseconds:
class ContractionHierarchy:
def __init__(self, graph):
self.graph = graph
self.shortcuts = {}
self.node_ordering = self.compute_importance_ordering()
def preprocess(self):
"""Contract vertices in importance order, adding shortcuts."""
for node in self.node_ordering:
self.contract(node)
def contract(self, node):
"""Remove node, add shortcut edges between its neighbors."""
for (u, w_u) in self.incoming(node):
for (v, w_v) in self.outgoing(node):
# If shortest u→v goes through node, add shortcut
if w_u + w_v < self.shortest_without(node, u, v):
self.add_shortcut(u, v, w_u + w_v)
def query(self, source, target):
"""Bidirectional Dijkstra on the hierarchy."""
# Forward search from source (only upward edges)
# Backward search from target (only upward edges)
# Meet at the highest node in both searches
passtradeoff / Preprocessing vs Query Speed
Contraction hierarchies are used by OSRM, GraphHopper, and Google Maps. They turn 100ms Dijkstra queries into 10μs hierarchy queries — essential for real-time navigation serving millions of concurrent users.
For static road networks (GPS), preprocessing is a one-time cost that enables millions of fast queries. For dynamic graphs (social networks), Dijkstra or A* without preprocessing is often better.
Synthesis
Beyond BFS and DFS, graph algorithms exploit structure to achieve dramatic speedups. A* uses heuristics to reduce search space. Bidirectional search cuts depth in half. Contraction hierarchies use preprocessing to enable microsecond queries on continent-scale road networks. Choose based on your graph size, dynamics, and query volume.