Compute the shortest paths and path lengths between nodes in the graph.
These algorithms work with undirected and directed graphs.
For directed graphs the paths can be computed in the reverse order by first flipping the edge orientation using R=G.reverse(copy=False).
| shortest_path(G[, source, target, weight]) | Compute 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. |
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]) | Compute 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. |
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 |
| astar_path_length(G, source, target[, ...]) | Return the length of the shortest path between source and target using |