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_path1(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    Returns:
 64        A list of vertices that form a shortest path.
 65    """
 66    weight_table, predecessor = shortest_path(graph, start, end, debug)
 67    path = []
 68
 69    current = end
 70    path.append(current)
 71    while current != start:
 72        current = predecessor[current]
 73        path.append(current)
 74        
 75    path.reverse()
 76
 77    if debug:
 78        print("predecessor table")
 79        print(predecessor)
 80
 81        print("weight table")
 82        print(weight_table)
 83        print("shortest path weight ", weight_table[end])
 84    return path
 85
 86
 87def find_path(graph: AdjacencyListWeightedGraph, start: str, end: str, debug: bool=False) -> list:
 88    """ 
 89    Return the shortest path of two vertices using Dijkstra's Algorithm.
 90
 91    Args:
 92        graph (AdjacencyListWeighted Graph): The graph to search.
 93        start (str): The starting vertex label.
 94        end (str): The ending vertex label.
 95        debug (bool): If True, display the weight table.
 96    
 97    Raises:
 98        KeyError: If there is no path from start to end.
 99
100    Returns:
101        A list of vertices that form a shortest path.
102    """
103    weight_table, predecessor = shortest_path(graph, start, end, debug)
104
105    # No path or invalid start/end
106    if end not in predecessor:
107        raise KeyError(f"No path from {start} to {end}.")
108
109    path = []
110    current = end
111    path.append(current)
112
113    while current != start:
114        current = predecessor[current]
115        path.append(current)
116
117    path.reverse()
118
119    if debug:
120        print("predecessor table")
121        print(predecessor)
122        print("weight table")
123        print(weight_table)
124        print("shortest path weight", weight_table[end])
125
126    return path