dijkstra_path
- compas.topology.dijkstra_path(adjacency, weight, source, target, dist=None)[source]
Find the shortest path between two nodes of a graph if the weights of the connecting edges are not all the same.
- Parameters
adjacency (dict[hashable, dict[hashable, None]] | dict[hashable, sequence[hashable]]) – An adjacency dictionary representing the connectivity of the graph by mapping nodes identifiers to neighbour identifiers. Examples of valid adjacency dicts are
{0: [1, 2, 3, 4], 1: [0], 2: [0], 3: [0], 4: [0]}
{0: {1: None, 2: None, 3: None, 4: None}, 1: {0: None}, 2: {0: None}, 3: {0: None}, 4: {0: None}}
weight (dict[tuple[hashable, hashable], float]) – A dictionary of edge weights.
source (hashable) – The start vertex.
target (hashable) – The end vertex.
- Returns
list[hashable] – 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.