Dijkstra's Algorithm Review
1graph = {
2 'A': [('C', 1), ('D', 4)],
3 'C': [('D', 2), ('E', 5)],
4 'D': [('B', 3)],
5 'E': [('B', 1)],
6 'B': [] # no outgoing edges
7}
We want the shortest path A → B. Use Dijkstra.
Dijkstra uses three main data structures:dist: best known distance from A to each nodeprev: to reconstruct the path (who is your best predecessor)pq: min-heap of (distance, node) for the frontier
From start node A:
dist[A] = 0
dist[others] = float(‘inf’)
prev[…] = None
pq = [(0, ‘A’)] (start with distance 0 to A)
visited = set() or we just rely on dist checks
1dist = {k: float('inf') for k in graph.keys()}
2prev = {k: None for k in graph.keys()}
3pq = [(0, 'A')]
4heapq.heapify(pq)
5visited = set()
6
7dist['A'] = 0
1while pq:
2 current_dist, current_node = heapq.heappop(pq)
3
4 # Skip if we've already found a better path to this node
5 if current_node in visited:
6 continue
7
8 visited.add(current_node)
9
10 # Explore neighbors
11 for neighbor, weight in graph[current_node]:
12 new_dist = current_dist + weight
13
14 # If we found a shorter path, update it
15 if new_dist < dist[neighbor]:
16 dist[neighbor] = new_dist
17 prev[neighbor] = current_node
18 heapq.heappush(pq, (new_dist, neighbor))
19
20# Result: shortest distance from A to B
21print(f"Shortest distance A → B: {dist['B']}") # Should be 7
22
23# Reconstruct path
24path = []
25node = 'B'
26while node is not None:
27 path.append(node)
28 node = prev[node]
29path.reverse()
30print(f"Path: {' → '.join(path)}") # Should be A → C → E → B
edit 11-16:
1import heapq
2
3graph = {
4 'A': [('C', 1), ('D', 4)],
5 'C': [('D', 2), ('E', 5)],
6 'D': [('B', 3)],
7 'E': [('B', 1)],
8 'B': [] # no outgoing edges
9}
10
11# shortest path from A to B
12def shortest_path_A_to_B(graph: dict):
13
14 dist = {k: float('inf') for k in graph.keys()}
15 parent = {k: None for k in graph.keys()}
16
17 dist['A'] = 0
18 pq = [(0, 'A')]
19 visited = set()
20
21 while pq:
22 cur_node_dist, cur_node = heapq.heappop(pq)
23
24 if cur_node in visited:
25 continue
26 visited.add(cur_node)
27
28 for child_node, child_node_dist in graph[cur_node]:
29 possibly_shorter_distance = cur_node_dist + child_node_dist
30 if possibly_shorter_distance < dist[child_node]: # if we can get to child_node in a shorter distance
31 dist[child_node] = possibly_shorter_distance
32 parent[child_node] = cur_node
33 heapq.heappush(pq, (possibly_shorter_distance, child_node))
34
35 return dist['B']
36
37print(shortest_path_A_to_B(graph))