rustworkx.digraph_k_shortest_path_lengths#

digraph_k_shortest_path_lengths(graph, start, k, edge_cost, /, goal=None)#

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 (PyGraph) – The graph to find the shortest paths in

  • 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:

PathLengthMapping

Raises:

ValueError – when an edge weight with NaN or negative value is provided.