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    Returns:
16        A tuple of a weight table hashtable and a predecesor hashtable.
17    """
18    weight_table = {}
19    predecessor = {}
20    visited = set()
21    h = MinHeap()
22
23    current = start
24    h.insert(current)
25    weight_table[current] = 0
26    predecessor[current] = current
27    
28    while not h.is_empty():
29        current_weight = weight_table.get(current, float('inf'))
30        visited.add(current)
31
32        for adjacent in graph[current]:
33            weight = graph[current][adjacent]
34            if adjacent not in visited:
35                h.insert(adjacent)
36
37            wt = weight_table.get(adjacent, float('inf'))
38            if wt > weight + current_weight:
39                weight_table[adjacent] = weight + current_weight
40                predecessor[adjacent] = current
41                if debug:
42                    print(weight_table)
43
44        current = h.pop()
45
46    return weight_table, predecessor
47
48def find_path(graph: AdjacencyListWeightedGraph, start: str, end: str, debug: bool=False) -> list:
49    """ 
50    Return the shortest path of two vertices using Dijkstra's Algorithm.
51
52    Args:
53        graph (AdjacencyListWeighted Graph): The graph to search.
54        start (str): The starting vertex label.
55        end (str): The ending vertex label.
56        debug (bool): If True, display the weight table.
57
58    Returns:
59        A list of vertices that form a shortest path.
60    """
61    weight_table, predecessor = shortest_path(graph, start, end, debug)
62    path = []
63
64    current = end
65    path.append(current)
66    while current != start:
67        current = predecessor[current]
68        path.append(current)
69        
70    path.reverse()
71
72    if debug:
73        print("predecessor table")
74        print(predecessor)
75
76        print("weight table")
77        print(weight_table)
78        print("shortest path weight ", weight_table[end])
79    return path