dsa.dijkstras

 1""" Module to access functions for Dijkstra's Algorithm. """
 2from dsa.heap import MinHeap
 3from dsa.graph import AdjacencyListWeightedGraph
 4
 5def shortest_path(graph: AdjacencyListWeightedGraph, start: str, end: str, debug: bool=False) -> tuple:
 6    """ 
 7    Helper function that returns a weight table and a predecessor table using Dijkstra's Algorithm.
 8
 9    Args:
10        graph (AdjacencyListWeighted Graph): The graph to search.
11        start (str): The starting vertex label.
12        end (str): The ending vertex label.
13        debug (bool): If True, display weight table as it is being built.
14    
15    Raises:
16        KeyError: If start or end vertex is not in the graph.
17        
18    Returns:
19        A tuple of a weight table hashtable and a predecessor predecessorhashtable.
20    """
21    if start not in graph:
22        raise KeyError(f"Start vertex {start} not in graph.")
23    if end not in graph:
24        raise KeyError(f"End vertex {end} not in graph.")
25
26    weight_table = {start: 0}
27    predecessor = {start: start}
28    visited = set()
29    pq = MinHeap()
30
31    pq.insert((0, start))
32    
33    while not pq.is_empty():
34        current_weight, current = pq.pop()
35        if current in visited:
36            continue
37        visited.add(current)
38
39        if current == end:
40            break
41
42        for adjacent, weight in graph[current].items():
43            new_dist = current_weight + weight
44            if new_dist < weight_table.get(adjacent, float('inf')):
45                weight_table[adjacent] = new_dist
46                predecessor[adjacent] = current
47                pq.insert((new_dist, adjacent))
48                if debug:
49                    print(weight_table)
50    
51    return weight_table, predecessor
52
53def find_path(graph: AdjacencyListWeightedGraph, start: str, end: str, debug: bool=False) -> list:
54    """ 
55    Return the shortest path of two vertices using Dijkstra's Algorithm.
56
57    Args:
58        graph (AdjacencyListWeighted Graph): The graph to search.
59        start (str): The starting vertex label.
60        end (str): The ending vertex label.
61        debug (bool): If True, display the weight table.
62    
63    Raises:
64        KeyError: If there is no path from start to end.
65
66    Returns:
67        A list of vertices that form a shortest path.
68    """
69    weight_table, predecessor = shortest_path(graph, start, end, debug)
70
71    # No path or invalid start/end
72    if end not in predecessor:
73        raise KeyError(f"No path from {start} to {end}.")
74
75    path = []
76    current = end
77    path.append(current)
78
79    while current != start:
80        current = predecessor[current]
81        path.append(current)
82
83    path.reverse()
84
85    if debug:
86        print("predecessor table")
87        print(predecessor)
88        print("weight table")
89        print(weight_table)
90        print("shortest path weight", weight_table[end])
91
92    return path