1"""
2Dijkstra's Algorithm - Shortest Path in Weighted Graphs
3
4Dijkstra's algorithm finds the shortest path from a source vertex to all other
5vertices in a weighted graph with non-negative edge weights. It uses a priority
6queue (min-heap) to always process the vertex with the smallest known distance.
7
8Key Properties:
9 - Finds shortest path in weighted graphs (minimum total weight)
10 - Only works with non-negative edge weights
11 - Greedy approach: always processes closest unvisited vertex
12 - Optimal: guaranteed to find shortest paths
13
14Time Complexity: O((V + E) log V) with binary heap
15Space Complexity: O(V) - distance dict + priority queue + predecessor dict
16
17Common Applications:
18 - GPS navigation (shortest route)
19 - Network routing protocols (OSPF)
20 - Social networks (degrees of separation with weights)
21 - Game AI pathfinding
22 - Flight booking (cheapest route)
23
24Graph Representation:
25 Uses adjacency list format for WEIGHTED graphs.
26 Format: {node: {neighbor: weight, ...}}
27"""
28
29import heapq
30from typing import Dict, List, Any, Tuple
31
32
33def dijkstra(graph: Dict[Any, Dict[Any, float]], start: Any) -> Dict[Any, float]:
34 """
35 Find shortest distances from start to all reachable vertices.
36
37 Args:
38 graph: Weighted adjacency list {node: {neighbor: weight, ...}}
39 start: Starting vertex
40
41 Returns:
42 Dictionary mapping each reachable vertex to its shortest distance
43
44 Raises:
45 ValueError: If start node is not in graph
46 """
47 if start not in graph:
48 raise ValueError(f"Start node '{start}' not in graph")
49
50 distances = {start: 0}
51 priority_queue = [(0, start)] # (distance, vertex)
52
53 while priority_queue:
54 current_dist, current = heapq.heappop(priority_queue)
55
56 # Skip if we've already found a shorter path
57 if current_dist > distances.get(current, float("inf")):
58 continue
59
60 for neighbor, weight in graph.get(current, {}).items():
61 distance = current_dist + weight
62
63 if distance < distances.get(neighbor, float("inf")):
64 distances[neighbor] = distance
65 heapq.heappush(priority_queue, (distance, neighbor))
66
67 return distances
68
69
70def dijkstra_with_path(graph: Dict[Any, Dict[Any, float]], start: Any) -> Tuple[Dict[Any, float], Dict[Any, Any]]:
71 """
72 Find shortest distances and track predecessors for path reconstruction.
73
74 Args:
75 graph: Weighted adjacency list {node: {neighbor: weight, ...}}
76 start: Starting vertex
77
78 Returns:
79 Tuple of (distances dict, predecessors dict)
80 - distances: {vertex: shortest_distance}
81 - predecessors: {vertex: previous_vertex_on_path}
82 """
83 if start not in graph:
84 raise ValueError(f"Start node '{start}' not in graph")
85
86 distances = {start: 0}
87 predecessors: Dict[Any, Any] = {start: None}
88 priority_queue = [(0, start)]
89
90 while priority_queue:
91 current_dist, current = heapq.heappop(priority_queue)
92
93 if current_dist > distances.get(current, float("inf")):
94 continue
95
96 for neighbor, weight in graph.get(current, {}).items():
97 distance = current_dist + weight
98
99 if distance < distances.get(neighbor, float("inf")):
100 distances[neighbor] = distance
101 predecessors[neighbor] = current
102 heapq.heappush(priority_queue, (distance, neighbor))
103
104 return distances, predecessors
105
106
107def shortest_path(graph: Dict[Any, Dict[Any, float]], start: Any, target: Any) -> Tuple[List[Any] | None, float]:
108 """
109 Find the shortest path and its total weight between two vertices.
110
111 Args:
112 graph: Weighted adjacency list {node: {neighbor: weight, ...}}
113 start: Starting vertex
114 target: Target vertex
115
116 Returns:
117 Tuple of (path as list of vertices, total distance)
118 Returns (None, inf) if no path exists
119 """
120 if start not in graph:
121 raise ValueError(f"Start node '{start}' not in graph")
122 if target not in graph:
123 raise ValueError(f"Target node '{target}' not in graph")
124
125 if start == target:
126 return [start], 0
127
128 distances, predecessors = dijkstra_with_path(graph, start)
129
130 if target not in distances:
131 return None, float("inf")
132
133 # Reconstruct path by backtracking from target
134 path = []
135 current = target
136 while current is not None:
137 path.append(current)
138 current = predecessors[current]
139
140 return path[::-1], distances[target]
141
142
143# Example usage and demonstration
144if __name__ == "__main__":
145 # Example weighted graph
146 #
147 # A ---4--- B
148 # | |
149 # 2 1
150 # | |
151 # C ---3--- D ---5--- E
152 #
153 example_graph = {
154 "A": {"B": 4, "C": 2},
155 "B": {"A": 4, "D": 1},
156 "C": {"A": 2, "D": 3},
157 "D": {"B": 1, "C": 3, "E": 5},
158 "E": {"D": 5},
159 }
160
161 print("Distances from A:", dijkstra(example_graph, "A"))
162
163 distances, predecessors = dijkstra_with_path(example_graph, "A")
164 print("Distances:", distances)
165 print("Predecessors:", predecessors)
166
167 path, distance = shortest_path(example_graph, "A", "E")
168 print(f"Shortest path A->E: {path} (distance: {distance})")
169
170 path, distance = shortest_path(example_graph, "A", "D")
171 print(f"Shortest path A->D: {path} (distance: {distance})")
172