Shortest Paths¶

Compute the shortest paths and path lengths between nodes in the graph.

These algorithms work with undirected and directed graphs.

`shortest_path`(G[, source, target, weight])	Compute shortest paths in the graph.
`all_shortest_paths`(G, source, target[, weight])	Compute all shortest paths in the graph.
`shortest_path_length`(G[, source, target, weight])	Compute shortest path lengths in the graph.
`average_shortest_path_length`(G[, weight])	Return the average shortest path length.
`has_path`(G, source, target)	Return True if G has a path from source to target, False otherwise.

Advanced Interface¶

Shortest path algorithms for unweighted graphs.

`single_source_shortest_path`(G, source[, cutoff])	Compute shortest path between source and all other nodes reachable from source.
`single_source_shortest_path_length`(G, source)	Compute the shortest path lengths from source to all reachable nodes.
`all_pairs_shortest_path`(G[, cutoff])	Compute shortest paths between all nodes.
`all_pairs_shortest_path_length`(G[, cutoff])	Computes the shortest path lengths between all nodes in `G`.
`predecessor`(G, source[, target, cutoff, ...])	Returns dictionary of predecessors for the path from source to all nodes in G.

Shortest path algorithms for weighed graphs.

`dijkstra_path`(G, source, target[, weight])	Returns the shortest path from source to target in a weighted graph G.
`dijkstra_path_length`(G, source, target[, weight])	Returns the shortest path length from source to target in a weighted graph.
`single_source_dijkstra_path`(G, source[, ...])	Compute shortest path between source and all other reachable nodes for a weighted graph.
`single_source_dijkstra_path_length`(G, source)	Compute the shortest path length between source and all other reachable nodes for a weighted graph.
`all_pairs_dijkstra_path`(G[, cutoff, weight])	Compute shortest paths between all nodes in a weighted graph.
`all_pairs_dijkstra_path_length`(G[, cutoff, ...])	Compute shortest path lengths between all nodes in a weighted graph.
`single_source_dijkstra`(G, source[, target, ...])	Compute shortest paths and lengths in a weighted graph G.
`bidirectional_dijkstra`(G, source, target[, ...])	Dijkstra’s algorithm for shortest paths using bidirectional search.
`dijkstra_predecessor_and_distance`(G, source)	Compute shortest path length and predecessors on shortest paths in weighted graphs.
`bellman_ford`(G, source[, weight])	Compute shortest path lengths and predecessors on shortest paths in weighted graphs.
`negative_edge_cycle`(G[, weight])	Return True if there exists a negative edge cycle anywhere in G.
`johnson`(G[, weight])	Compute shortest paths between all nodes in a weighted graph using Johnson’s algorithm.

Floyd-Warshall algorithm for shortest paths.

`floyd_warshall`(G[, weight])	Find all-pairs shortest path lengths using Floyd’s algorithm.
`floyd_warshall_predecessor_and_distance`(G[, ...])	Find all-pairs shortest path lengths using Floyd’s algorithm.
`floyd_warshall_numpy`(G[, nodelist, weight])	Find all-pairs shortest path lengths using Floyd’s algorithm.

Shortest paths and path lengths using A* (“A star”) algorithm.

`astar_path`(G, source, target[, heuristic, ...])	Return a list of nodes in a shortest path between source and target using the A* (“A-star”) algorithm.
`astar_path_length`(G, source, target[, ...])	Return the length of the shortest path between source and target using the A* (“A-star”) algorithm.