Dijkstra's Algorithm Implementations
Table of Contents
1. Introduction
This document explores different implementations of Dijkstra's algorithm using Python's defaultdict.
2. Graph Representations
2.1. List of Tuples Approach
from collections import defaultdict
from heapq import heappush, heappop
import math
class GraphTuple:
def __init__(self):
# Initialize graph as defaultdict of lists containing (node, weight) tuples
self.graph = defaultdict(list)
def add_edge(self, source, dest, weight):
"""Add an edge to the graph"""
self.graph[source].append((dest, weight))
# For undirected graph, add reverse edge
self.graph[dest].append((source, weight))
def find_paths(self, start):
"""Find shortest paths from start node"""
distances = defaultdict(lambda: math.inf)
distances[start] = 0
pq = [(0, start)]
paths = defaultdict(list)
paths[start] = [start]
visited = set()
while pq:
curr_dist, curr = heappop(pq)
if curr in visited:
continue
visited.add(curr)
for neighbor, weight in self.graph[curr]:
distance = curr_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
paths[neighbor] = paths[curr] + [neighbor]
heappush(pq, (distance, neighbor))
return distances, paths
# Example usage and test
def test_tuple_implementation():
g = GraphTuple()
edges = [
('A', 'B', 4), ('A', 'C', 2),
('B', 'C', 1), ('B', 'D', 5),
('C', 'D', 8), ('C', 'E', 10),
('D', 'E', 2), ('D', 'F', 6),
('E', 'F', 3)
]
for source, dest, weight in edges:
g.add_edge(source, dest, weight)
distances, paths = g.find_paths('A')
return distances, paths
if __name__ == "__main__":
distances, paths = test_tuple_implementation()
for node in sorted(distances.keys()):
print(f"Distance to {node}: {distances[node]}")
print(f"Path: {' -> '.join(paths[node])}\n")
2.2. Nested DefaultDict Approach
from collections import defaultdict
from heapq import heappush, heappop
import math
class GraphNested:
def __init__(self):
# Initialize graph as nested defaultdict
self.graph = defaultdict(lambda: defaultdict(int))
def add_edge(self, source, dest, weight):
"""Add an edge to the graph"""
self.graph[source][dest] = weight
# For undirected graph, add reverse edge
self.graph[dest][source] = weight
def find_paths(self, start):
"""Find shortest paths from start node"""
distances = defaultdict(lambda: math.inf)
distances[start] = 0
pq = [(0, start)]
paths = defaultdict(list)
paths[start] = [start]
visited = set()
while pq:
curr_dist, curr = heappop(pq)
if curr in visited:
continue
visited.add(curr)
for neighbor, weight in self.graph[curr].items():
distance = curr_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
paths[neighbor] = paths[curr] + [neighbor]
heappush(pq, (distance, neighbor))
return distances, paths
# Example usage and test
def test_nested_implementation():
g = GraphNested()
edges = [
('A', 'B', 4), ('A', 'C', 2),
('B', 'C', 1), ('B', 'D', 5),
('C', 'D', 8), ('C', 'E', 10),
('D', 'E', 2), ('D', 'F', 6),
('E', 'F', 3)
]
for source, dest, weight in edges:
g.add_edge(source, dest, weight)
distances, paths = g.find_paths('A')
return distances, paths
if __name__ == "__main__":
distances, paths = test_nested_implementation()
for node in sorted(distances.keys()):
print(f"Distance to {node}: {distances[node]}")
print(f"Path: {' -> '.join(paths[node])}\n")
4. Performance Comparison
import time
from dykstra_tuple import GraphTuple
from dykstra_nested import GraphNested
def benchmark_comparison(num_nodes=1000, num_edges=5000):
"""Compare performance of both implementations"""
# Generate test data
import random
edges = [(str(random.randint(0, num_nodes)),
str(random.randint(0, num_nodes)),
random.randint(1, 100))
for _ in range(num_edges)]
# Test tuple implementation
start_time = time.time()
g_tuple = GraphTuple()
for source, dest, weight in edges:
g_tuple.add_edge(source, dest, weight)
tuple_dist, _ = g_tuple.find_paths('0')
tuple_time = time.time() - start_time
# Test nested implementation
start_time = time.time()
g_nested = GraphNested()
for source, dest, weight in edges:
g_nested.add_edge(source, dest, weight)
nested_dist, _ = g_nested.find_paths('0')
nested_time = time.time() - start_time
print(f"Tuple Implementation Time: {tuple_time:.4f} seconds")
print(f"Nested Implementation Time: {nested_time:.4f} seconds")
if __name__ == "__main__":
benchmark_comparison()
5. Memory Usage Analysis
import sys
from dykstra_tuple import GraphTuple
from dykstra_nested import GraphNested
def analyze_memory():
"""Compare memory usage of both implementations"""
# Create small test graph
edges = [
('A', 'B', 4), ('A', 'C', 2),
('B', 'C', 1), ('B', 'D', 5),
('C', 'D', 8), ('C', 'E', 10),
('D', 'E', 2), ('D', 'F', 6),
('E', 'F', 3)
]
# Measure tuple implementation
g_tuple = GraphTuple()
for source, dest, weight in edges:
g_tuple.add_edge(source, dest, weight)
tuple_size = sys.getsizeof(g_tuple.graph)
# Measure nested implementation
g_nested = GraphNested()
for source, dest, weight in edges:
g_nested.add_edge(source, dest, weight)
nested_size = sys.getsizeof(g_nested.graph)
print(f"Tuple Implementation Memory: {tuple_size} bytes")
print(f"Nested Implementation Memory: {nested_size} bytes")
if __name__ == "__main__":
analyze_memory()
6. Usage Notes and Trade-offs
6.1. Tuple Implementation Benefits
- More memory efficient for sparse graphs
- Simple append operation for adding edges
- Natural for graphs with fixed edge weights
- Better for sequential edge traversal
6.2. Nested Dict Implementation Benefits
- Faster edge weight lookups
- Easier to modify edge weights
- More intuitive adjacency list representation
- Better for dense graphs
- Simpler to check edge existence
6.3. When to Use Each
Use Tuple Implementation when:
- Memory is constrained
- Graph is sparse
- Edge weights rarely change
- Sequential edge traversal is common
Use Nested Dict Implementation when:
- Quick edge lookups are needed
- Edge weights change frequently
- Graph is dense
- Random access to edges is common
- Edge existence checks are frequent