rustworkx.k_shortest_path_lengths#

k_shortest_path_lengths(graph, start, k, edge_cost, goal=None)[source]#

Compute the length of the kth shortest path

Computes the lengths of the kth shortest path from start to every reachable node.

Computes in \(O(k * (|E| + |V|*log(|V|)))\) time (average).

Parameters:

  • graph – The graph to find the shortest paths in. Can either be a PyGraph or PyDiGraph

  • start (int) – The node index to find the shortest paths from

  • k (int) – The kth shortest path to find the lengths of

  • edge_cost – A python callable that will receive an edge payload and return a float for the cost of that eedge

  • goal (int) – An optional goal node index, if specified the output dictionary

Returns:

A dict of lengths where the key is the destination node index and the value is the length of the path.

Return type:

dict