dijkstra_path

compas.topology.dijkstra_path(adjacency, weight, source, target, dist=None)[source]

Find the shortest path between two vertices if the edge weights are not all the same.

Parameters

  • adjacency (dict) – An adjacency dictionary. Each key represents a vertex and maps to a list of neighboring vertex keys.

  • weight (dict) – A dictionary of edge weights.

  • source (str) – The start vertex.

  • target (str) – The end vertex.

Returns

list – The shortest path.

Notes

The edge weights should all be positive. For a directed graph, set the weights of the reversed edges to +inf. For an undirected graph, add the same weight for an edge in both directions.

Examples

>>>