pyemap.shortest_paths.yens_shortest_paths

pyemap.shortest_paths.yens_shortest_paths(G, start, target, max_paths=10)[source]

Returns shortest paths from source to target.

Uses Yen’s algorithm to calculate the shortest paths from source to target, writes out the ShortestPath objects to file, and returns the 10 pathway IDs. In the graph, nodes and edges that are part of any pathways are made opaque, and the shortest path is highlighted.

Parameters:

  • G (networkx.Graph object) – Undirected, weighted residue graph

  • start (str) – Source node

  • target (str) – Target node

  • max_paths (int, optional) – Maximum number of paths to search for

Returns:

A list of length 1 containing a single Branch object which represents the group of pathways found.

Return type:

list of Branch objects

References

Jin Y. Yen, Finding the K Shortest Loopless Paths in a Network, Management Science, Vol. 17, No. 11, Theory Series (Jul., 1971), pp. 712-716.

Raises:

PyeMapShortestPathException: – No shortest paths to target found.