Module path

Return the shortest path length in the graph G between the source and target. Raise an exception if no path exists.

G is treated as an unweighted graph. For weighted graphs see dijkstra_path_length.

Shortest path length from source to all reachable nodes.

Returns a dictionary of shortest path lengths keyed by target.

>>> G=path_graph(5)
>>> length=single_source_shortest_path_length(G,1)
>>> length[4]
3
>>> print length
{0: 1, 1: 0, 2: 1, 3: 2, 4: 3}

cutoff is optional integer depth to stop the search - only paths of length <= cutoff are returned.

Return dictionary of shortest path lengths between all nodes in G.

The dictionary only has keys for reachable node pairs. >>> G=path_graph(5) >>> length=all_pairs_shortest_path_length(G) >>> print length[1][4] 3 >>> length[1] {0: 1, 1: 0, 2: 1, 3: 2, 4: 3}

cutoff is optional integer depth to stop the search - only paths of length <= cutoff are returned.

Return a list of nodes in G for a shortest path between source and target.

There may be more than one shortest path. This returns only one.

Return list of nodes in a shortest path between source and target. Return False if no path exists.

Also known as shortest_path.

Return list of nodes in a shortest path between source and all other nodes in G reachable from source.

There may be more than one shortest path between the source and target nodes - this routine returns only one.

cutoff is optional integer depth to stop the search - only paths of length <= cutoff are returned.

See also shortest_path and bidirectional_shortest_path.

Return dictionary of shortest paths between all nodes in G.

The dictionary only has keys for reachable node pairs.

cutoff is optional integer depth to stop the search - only paths of length <= cutoff are returned.

See also floyd_warshall.

Returns the shortest path from source to target in a weighted graph G. Uses a bidirectional version of Dijkstra's algorithm.

Edge data must be numerical values for XGraph and XDiGraphs. The weights are assigned to be 1 for Graphs and DiGraphs.

See also bidirectional_dijkstra for more information about the algorithm.

Returns the shortest path length from source to target in a weighted graph G. Uses a bidirectional version of Dijkstra's algorithm.

Edge data must be numerical values for XGraph and XDiGraphs. The weights are assigned to be 1 for Graphs and DiGraphs.

See also bidirectional_dijkstra for more information about the algorithm.

Dijkstra's algorithm for shortest paths using bidirectional search.

Returns a two-tuple (d,p) where d is the distance and p is the path from the source to the target.

Distances are calculated as sums of weighted edges traversed.

Edges must hold numerical values for XGraph and XDiGraphs. The weights are set to 1 for Graphs and DiGraphs.

In practice bidirectional Dijkstra is much more than twice as fast as ordinary Dijkstra.

Ordinary Dijkstra expands nodes in a sphere-like manner from the source. The radius of this sphere will eventually be the length of the shortest path. Bidirectional Dijkstra will expand nodes from both the source and the target, making two spheres of half this radius. Volume of the first sphere is pi*r*r while the others are 2*pi*r/2*r/2, making up half the volume.

This algorithm is not guaranteed to work if edge weights are negative or are floating point numbers (overflows and roundoff errors can cause problems).

Returns the shortest paths from source to all other reachable nodes in a weighted graph G. Uses Dijkstra's algorithm.

Returns a dictionary of shortest path lengths keyed by source.

Edge data must be numerical values for XGraph and XDiGraphs. The weights are assigned to be 1 for Graphs and DiGraphs.

See also single_source_dijkstra for more information about the algorithm.

Returns the shortest path lengths from source to all other reachable nodes in a weighted graph G. Uses Dijkstra's algorithm.

Returns a dictionary of shortest path lengths keyed by source.

Edge data must be numerical values for XGraph and XDiGraphs. The weights are assigned to be 1 for Graphs and DiGraphs.

See also single_source_dijkstra for more information about the algorithm.

Dijkstra's algorithm for shortest paths in a weighted graph G.

Use:

single_source_dijkstra_path() - shortest path list of nodes

single_source_dijkstra_path_length() - shortest path length

Returns a tuple of two dictionaries keyed by node. The first stores distance from the source. The second stores the path from the source to that node.

Distances are calculated as sums of weighted edges traversed. Edges must hold numerical values for XGraph and XDiGraphs. The weights are 1 for Graphs and DiGraphs.

Optional target argument stops the search when target is found.

Based on the Python cookbook recipe (119466) at http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466

This algorithm is not guaranteed to work if edge weights are negative or are floating point numbers (overflows and roundoff errors can cause problems).

See also 'bidirectional_dijkstra_path'

Same algorithm as for single_source_dijsktra, but returns two dicts representing a list of predecessors of a node and the distance to each node respectively. The list of predecessors contains more than one element only when there are more than one shortest paths to the key node.

This routine is intended for use with the betweenness centrality algorithms in centrality.py.

The Floyd-Warshall algorithm for all pairs shortest paths.

Returns a tuple (distance,path) containing two arrays of shortest distance and paths as a predecessor matrix.

This differs from floyd_warshall only in the types of the return values. Thus, path[i,j] gives the predecessor at j on a path from i to j. A value of None indicates that no path exists. A predecessor of i indicates the beginning of the path. The advantage of this implementation is that, while running time is O(n^3), running space is O(n^2).

This algorithm handles negative weights.

The Floyd-Warshall algorithm for all pairs shortest paths.

Returns a tuple (distance,path) containing two dictionaries of shortest distance and predecessor paths.

This algorithm is most appropriate for dense graphs. The running time is O(n^3), and running space is O(n^2) where n is the number of nodes in G.

For sparse graphs, see

all_pairs_shortest_path all_pairs_shortest_path_length

which are based on Dijkstra's algorithm.

Returns dictionary of predecessors for the path from source to all nodes in G.

Optional target returns only predecessors between source and target. Cutoff is a limit on the number of hops traversed.

Example for the path graph 0-1-2-3

>>> G=path_graph(4)
>>> print G.nodes()
[0, 1, 2, 3]
>>> predecessor(G,0)
{0: [], 1: [0], 2: [1], 3: [2]}