Dijkstra's Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

import heapq
from typing import Dict, List, Any, Tuple


def dijkstra(graph: Dict[Any, Dict[Any, float]], start: Any) -> Dict[Any, float]:
    """
    Find shortest distances from start to all reachable vertices.

    Args:
        graph: Weighted adjacency list {node: {neighbor: weight, ...}}
        start: Starting vertex

    Returns:
        Dictionary mapping each reachable vertex to its shortest distance

    Raises:
        ValueError: If start node is not in graph
    """
    if start not in graph:
        raise ValueError(f"Start node '{start}' not in graph")

    distances = {start: 0}
    priority_queue = [(0, start)]  # (distance, vertex)

    while priority_queue:
        current_dist, current = heapq.heappop(priority_queue)

        # Skip if we've already found a shorter path
        if current_dist > distances.get(current, float("inf")):
            continue

        for neighbor, weight in graph.get(current, {}).items():
            distance = current_dist + weight

            if distance < distances.get(neighbor, float("inf")):
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances


def dijkstra_with_path(graph: Dict[Any, Dict[Any, float]], start: Any) -> Tuple[Dict[Any, float], Dict[Any, Any]]:
    """
    Find shortest distances and track predecessors for path reconstruction.

    Args:
        graph: Weighted adjacency list {node: {neighbor: weight, ...}}
        start: Starting vertex

    Returns:
        Tuple of (distances dict, predecessors dict)
        - distances: {vertex: shortest_distance}
        - predecessors: {vertex: previous_vertex_on_path}
    """
    if start not in graph:
        raise ValueError(f"Start node '{start}' not in graph")

    distances = {start: 0}
    predecessors: Dict[Any, Any] = {start: None}
    priority_queue = [(0, start)]

    while priority_queue:
        current_dist, current = heapq.heappop(priority_queue)

        if current_dist > distances.get(current, float("inf")):
            continue

        for neighbor, weight in graph.get(current, {}).items():
            distance = current_dist + weight

            if distance < distances.get(neighbor, float("inf")):
                distances[neighbor] = distance
                predecessors[neighbor] = current
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances, predecessors


def shortest_path(graph: Dict[Any, Dict[Any, float]], start: Any, target: Any) -> Tuple[List[Any] | None, float]:
    """
    Find the shortest path and its total weight between two vertices.

    Args:
        graph: Weighted adjacency list {node: {neighbor: weight, ...}}
        start: Starting vertex
        target: Target vertex

    Returns:
        Tuple of (path as list of vertices, total distance)
        Returns (None, inf) if no path exists
    """
    if start not in graph:
        raise ValueError(f"Start node '{start}' not in graph")
    if target not in graph:
        raise ValueError(f"Target node '{target}' not in graph")

    if start == target:
        return [start], 0

    distances, predecessors = dijkstra_with_path(graph, start)

    if target not in distances:
        return None, float("inf")

    # Reconstruct path by backtracking from target
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = predecessors[current]

    return path[::-1], distances[target]


# Example usage and demonstration
if __name__ == "__main__":
    # Example weighted graph
    #
    #       A ---4--- B
    #       |         |
    #       2         1
    #       |         |
    #       C ---3--- D ---5--- E
    #
    example_graph = {
        "A": {"B": 4, "C": 2},
        "B": {"A": 4, "D": 1},
        "C": {"A": 2, "D": 3},
        "D": {"B": 1, "C": 3, "E": 5},
        "E": {"D": 5},
    }

    print("Distances from A:", dijkstra(example_graph, "A"))

    distances, predecessors = dijkstra_with_path(example_graph, "A")
    print("Distances:", distances)
    print("Predecessors:", predecessors)

    path, distance = shortest_path(example_graph, "A", "E")
    print(f"Shortest path A->E: {path} (distance: {distance})")

    path, distance = shortest_path(example_graph, "A", "D")
    print(f"Shortest path A->D: {path} (distance: {distance})")