dsap.graph.shortest_paths

module documentation

Provides shortest_path_distances and shortest_path_tree functions for computing shortest paths in a weighted graph.

Function shortest_path_distances Compute shortest-path distances from src to reachable vertices of g.
Function shortest_path_tree Reconstruct shortest-path tree rooted at vertex s, given distance map D.
def shortest_path_distances(g, src):

Compute shortest-path distances from src to reachable vertices of g.

Graph g can be undirected or directed, but must be weighted such that e.element() returns a numeric weight for each edge e.

Return dictionary mapping each reachable vertex to its distance from src.

def shortest_path_tree(g, s, D):

Reconstruct shortest-path tree rooted at vertex s, given distance map D.

Return tree as a map from each reachable vertex v (other than s) to the edge e=(u,v) that is used to reach v from its parent u in the tree.