Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest paths from a single source vertex to all other vertices in a weighted graph with non-negative edge weights.

Algorithm Overview

Dijkstra's algorithm uses a greedy approach with a priority queue to efficiently find shortest paths. It maintains a set of vertices whose shortest distance from the source is known, and progressively adds vertices with the minimum tentative distance.

Key Features

Single-Source: Finds shortest paths from one source to all other vertices
Non-Negative Weights: Requires all edge weights to be non-negative
Optimal: Guarantees finding the actual shortest paths
Efficient: O((V + E) log V) time complexity with binary heap

Available Functions

Usage Examples

Basic Shortest Path

from algo.data_structs.graphs import AdjacencyListGraph
from algo.algorithms.graphs import dijkstra

# Create a transportation network
network = AdjacencyListGraph(directed=True)
network.add_edge('Home', 'Work', 15)      # 15 minutes
network.add_edge('Home', 'Store', 10)     # 10 minutes  
network.add_edge('Store', 'Work', 8)      # 8 minutes
network.add_edge('Work', 'Gym', 5)        # 5 minutes
network.add_edge('Store', 'Gym', 12)      # 12 minutes

# Find shortest times from Home to all locations
distances = dijkstra(network, 'Home')

print("Shortest travel times from Home:")
for location, time in distances.items():
    if time != float('inf'):
        print(f"  {location}: {time} minutes")

# Output:
# Home: 0 minutes
# Store: 10 minutes  
# Work: 18 minutes (Home -> Store -> Work)
# Gym: 23 minutes (Home -> Store -> Work -> Gym)

Path Reconstruction

from algo.algorithms.graphs import dijkstra_with_path

# Find specific route with path details
result = dijkstra_with_path(network, 'Home', 'Gym')

if result:
    distance, path = result
    print(f"Best route to Gym: {' -> '.join(path)}")
    print(f"Total time: {distance} minutes")

    # Analyze the route
    for i in range(len(path) - 1):
        from_loc = path[i]
        to_loc = path[i + 1]
        segment_time = network.get_edge_weight(from_loc, to_loc)
        print(f"  {from_loc} to {to_loc}: {segment_time} minutes")

Multiple Destinations

from algo.algorithms.graphs import dijkstra_all_paths

# Plan trips to multiple destinations
destinations = dijkstra_all_paths(network, 'Home')

print("All possible trips from Home:")
for location, (distance, path) in destinations.items():
    if location != 'Home':
        print(f"\nTo {location}:")
        print(f"  Route: {' -> '.join(path)}")
        print(f"  Time: {distance} minutes")
        print(f"  Stops: {len(path) - 1}")

Network Analysis

# Analyze network connectivity and efficiency
def analyze_network_efficiency(graph):
    """Analyze average travel times and connectivity."""
    vertices = list(graph.get_vertices())
    total_reachable_pairs = 0
    total_distance = 0
    max_distance = 0

    for start in vertices:
        distances = dijkstra(graph, start)

        for end, distance in distances.items():
            if start != end and distance != float('inf'):
                total_reachable_pairs += 1
                total_distance += distance
                max_distance = max(max_distance, distance)

    if total_reachable_pairs > 0:
        avg_distance = total_distance / total_reachable_pairs
        connectivity = total_reachable_pairs / (len(vertices) * (len(vertices) - 1))

        return {
            'average_distance': avg_distance,
            'max_distance': max_distance,
            'connectivity': connectivity,
            'reachable_pairs': total_reachable_pairs
        }

    return {'connectivity': 0}

analysis = analyze_network_efficiency(network)
print(f"\nNetwork Analysis:")
print(f"  Average travel time: {analysis['average_distance']:.1f} minutes")
print(f"  Maximum travel time: {analysis['max_distance']} minutes")
print(f"  Connectivity: {analysis['connectivity']:.1%}")

Handling Edge Cases

# Check for algorithm compatibility
from algo.algorithms.graphs import has_negative_weights

if has_negative_weights(network):
    print("Warning: Graph has negative weights. Use Floyd-Warshall instead.")
else:
    print("Graph is compatible with Dijkstra's algorithm.")

# Handle unreachable destinations
result = dijkstra_with_path(network, 'Gym', 'Home')
if result is None:
    print("No path exists from Gym to Home")
else:
    distance, path = result
    print(f"Return trip: {' -> '.join(path)} ({distance} minutes)")

# Handle non-existent vertices
distances = dijkstra(network, 'NonExistent')
if not distances:
    print("Start vertex does not exist in graph")

Real-World Applications

# Model a city street network
city = AdjacencyListGraph(directed=True)

# Add streets with travel times (in minutes)
streets = [
    ('1st_Ave', '2nd_Ave', 3),
    ('2nd_Ave', '3rd_Ave', 4),
    ('1st_Ave', 'Main_St', 2),
    ('Main_St', '2nd_Ave', 2),
    ('2nd_Ave', 'Park_St', 5),
    ('3rd_Ave', 'Park_St', 3),
]

for from_street, to_street, time in streets:
    city.add_edge(from_street, to_street, time)

# Find fastest route
route = dijkstra_with_path(city, '1st_Ave', 'Park_St')
if route:
    time, path = route
    print(f"Fastest route: {' -> '.join(path)} ({time} min)")

Network Routing

# Model computer network with latencies
network_topology = AdjacencyListGraph(directed=False)

# Add network links with latencies (ms)
links = [
    ('Router_A', 'Router_B', 10),
    ('Router_B', 'Router_C', 15),
    ('Router_A', 'Router_D', 20),
    ('Router_D', 'Router_C', 5),
    ('Router_C', 'Server', 8),
]

for router1, router2, latency in links:
    network_topology.add_edge(router1, router2, latency)

# Find lowest latency path to server
path_info = dijkstra_with_path(network_topology, 'Router_A', 'Server')
if path_info:
    latency, path = path_info
    print(f"Optimal route to server: {' -> '.join(path)}")
    print(f"Total latency: {latency}ms")

Performance Characteristics

Time Complexity

Binary Heap: O((V + E) log V)
Fibonacci Heap: O(E + V log V) - theoretical optimum
Array Implementation: O(V²) - suitable for dense graphs

Space Complexity

Memory Usage: O(V) for distances and priority queue
Path Storage: O(V²) for all paths (dijkstra_all_paths)

Graph Type Impact

Graph Type	Time Complexity	Best Use Case
Sparse (E ≈ V)	O(V log V)	Large networks with few connections
Dense (E ≈ V²)	O(V² log V)	Consider Floyd-Warshall for all-pairs

Algorithm Limitations

Negative Weights

Dijkstra's algorithm does not work with negative edge weights:

# This will produce incorrect results
bad_graph = AdjacencyListGraph(directed=True)
bad_graph.add_edge('A', 'B', 10)
bad_graph.add_edge('A', 'C', 5)
bad_graph.add_edge('C', 'B', -8)  # Negative weight!

# Always check before using Dijkstra
if has_negative_weights(bad_graph):
    print("Use Floyd-Warshall or Bellman-Ford for negative weights")

Single Source

For all-pairs shortest paths, consider Floyd-Warshall:

# Inefficient: Running Dijkstra for each vertex
vertices = list(graph.get_vertices())
all_distances = {}
for start in vertices:
    all_distances[start] = dijkstra(graph, start)

# Better: Use Floyd-Warshall for all-pairs
from algo.algorithms.graphs import floyd_warshall
all_distances = floyd_warshall(graph)

Best Practices

Validate Input: Check for negative weights before running
Choose Right Variant: Use specific functions based on your needs
Handle Edge Cases: Check for None returns and infinite distances
Consider Alternatives: Floyd-Warshall for small dense graphs or negative weights
Memory Management: Use dijkstra() instead of dijkstra_all_paths() for large graphs when you don't need all paths

API Reference

Dijkstra's algorithm for finding shortest paths from a single source vertex.

This module provides an implementation of Dijkstra's algorithm that works with any graph implementation following the Graph interface.

`dijkstra(graph, start)`

Find shortest paths from a source vertex to all other vertices using Dijkstra's algorithm.

Parameters:

Name	Type	Description	Default
`graph`	`Graph`	A graph implementation following the Graph interface	required
`start`	`Any`	Starting vertex	required

Returns:

Type	Description
`Dict[Any, float]`	A dictionary mapping vertices to their shortest distances from start

Time Complexity: O((V + E) log V) where V is vertices and E is edges Space Complexity: O(V)

Note: This algorithm doesn't work with negative edge weights.

`dijkstra_all_paths(graph, start)`

Find shortest paths from a source vertex to all other reachable vertices.

Parameters:

Name	Type	Description	Default
`graph`	`Graph`	A graph implementation following the Graph interface	required
`start`	`Any`	Starting vertex	required

Returns:

Type	Description
`Dict[Any, Tuple[float, List[Any]]]`	A dictionary mapping vertices to (distance, path) tuples

`dijkstra_with_path(graph, start, end)`

Find the shortest path between two vertices using Dijkstra's algorithm with path reconstruction.

Parameters:

Name	Type	Description	Default
`graph`	`Graph`	A graph implementation following the Graph interface	required
`start`	`Any`	Starting vertex	required
`end`	`Any`	Ending vertex	required

Returns:

Type	Description
`Optional[Tuple[float, List[Any]]]`	A tuple of (distance, path) if path exists, None otherwise
`Optional[Tuple[float, List[Any]]]`	The path is a list of vertices from start to end

`has_negative_weights(graph)`

Check if the graph has any negative edge weights.

Dijkstra's algorithm doesn't work correctly with negative weights.

Parameters:

Name	Type	Description	Default
`graph`	`Graph`	A graph implementation following the Graph interface	required

Returns:

Type	Description
`bool`	True if any edge has negative weight, False otherwise

Dijkstra's Algorithm

Algorithm Overview

Key Features

Available Functions

Usage Examples

Basic Shortest Path

Path Reconstruction

Multiple Destinations

Network Analysis

Handling Edge Cases

Real-World Applications

GPS Navigation System

Network Routing

Performance Characteristics

Time Complexity

Space Complexity

Graph Type Impact

Algorithm Limitations

Negative Weights

Single Source

Best Practices

API Reference

dijkstra(graph, start)

dijkstra_all_paths(graph, start)

dijkstra_with_path(graph, start, end)

has_negative_weights(graph)

`dijkstra(graph, start)`

`dijkstra_all_paths(graph, start)`

`dijkstra_with_path(graph, start, end)`

`has_negative_weights(graph)`