home > research > dijkstra (2025-07-30)

Dijkstra's Algorithm Implementations

Dijkstra's Algorithm Implementations

Table of Contents

Introduction

This document explores different implementations of Dijkstra's algorithm using Python's defaultdict.

Graph Representations

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")

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")

Algorithm Flow Diagrams

Tuple Implementation Flow

graph TD
    A[Start] --> B[Initialize Graph<br>defaultdict(list)]
    B --> C[Add Edge<br>graph[source].append((dest, weight))]
    C --> D[Initialize Dijkstra<br>distances, pq, paths]
    D --> E{Priority Queue Empty?}
    E -->|No| F[Get Next Node<br>heappop]
    F --> G{Node Visited?}
    G -->|No| H[Process Node<br>Update Distances/Paths]
    H --> I[Add to Visited]
    I --> J[Process Neighbors<br>Iterate through tuples]
    J --> K{Better Path Found?}
    K -->|Yes| L[Update Distance<br>Update Path<br>Add to Queue]
    L --> E
    K -->|No| E
    G -->|Yes| E
    E -->|Yes| M[Return Results]

Nested Dict Implementation Flow

graph TD
    A[Start] --> B[Initialize Graph<br>defaultdict(lambda: defaultdict(int))]
    B --> C[Add Edge<br>graph[source][dest] = weight]
    C --> D[Initialize Dijkstra<br>distances, pq, paths]
    D --> E{Priority Queue Empty?}
    E -->|No| F[Get Next Node<br>heappop]
    F --> G{Node Visited?}
    G -->|No| H[Process Node<br>Update Distances/Paths]
    H --> I[Add to Visited]
    I --> J[Process Neighbors<br>Iterate through items()]
    J --> K{Better Path Found?}
    K -->|Yes| L[Update Distance<br>Update Path<br>Add to Queue]
    L --> E
    K -->|No| E
    G -->|Yes| E
    E -->|Yes| M[Return Results]

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()

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()

Usage Notes and Trade-offs

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

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

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

Local Variables

Author: Claude

jwalsh@nexus

Last Updated: 2025-07-30 13:45:27

build: 2025-12-23 09:11 | sha: a10ddd7