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, weighted]) | Compute shortest paths in the graph. |
| shortest_path_length(G[, source, target, ...]) | Compute shortest path lengths in the graph. |
| average_shortest_path_length(G[, weighted]) | Return the average shortest path length. |
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 |
| floyd_warshall(G) | The Floyd-Warshall algorithm for all pairs shortest paths. |
Shortest path algorithms for weighed graphs.
| dijkstra_path(G, source, target[, weight]) | Returns the shortest path from source to target in a weighted |
| dijkstra_path_length(G, source, target[, weight]) | Returns the shortest path length from source to target in a weighted |
| single_source_dijkstra_path(G, source[, weight]) | Compute shortest path between source and all other reachable nodes for a weighted graph. |
| single_source_dijkstra_path_length(G, source) | Compute shortest path length between source and all other reachable nodes for a weighted graph. |
| all_pairs_dijkstra_path(G[, weight]) | Compute shortest paths between all nodes in a weighted graph. |
| all_pairs_dijkstra_path_length(G[, weight]) | 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. |
| bidirectional_shortest_path(G, source, target) | Return a list of nodes in a shortest path between source and target. |
| dijkstra_predecessor_and_distance(G, source) | Compute shorest path length and predecessors on shortest paths in weighted graphs. |
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[, heuristic]) | Return a list of nodes in a shortest path between source and target |