dsa.dijkstra module
Module to access functions for Dijkstra’s Algorithm.
- dsa.dijkstra.find_path(graph, start, end, debug=False)
Return the shortest path of two vertices using Dijkstra’s Algorithm.
- Parameters:
graph (Graph) – The graph to search.
start (str) – The starting vertex label.
end (str) – The ending vertex label.
debug (bool) – If True, display the weight table.
- Raises:
KeyError – If start or end vertex is not in the graph, or if there is no path from start to end.
- Return type:
list- Returns:
A list of vertices that form a shortest path.
- dsa.dijkstra.shortest_path(graph, start, end, debug=False)
Helper function that returns a weight table and a predecessor table using Dijkstra’s Algorithm.
- Parameters:
graph (Graph) – The graph to search.
start (str) – The starting vertex label.
end (str) – The ending vertex label.
debug (bool) – If True, display weight table as it is being built.
- Raises:
KeyError – If start or end vertex is not in the graph.
- Return type:
tuple- Returns:
A tuple of a weight table hashtable and a predecessor hashtable.