Compute the shortest paths and path lengths between nodes in the graph.
| 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) | Returns the shortest path from source to target in a weighted |
| dijkstra_path_length(G, source, target) | Returns the shortest path length from source to target in a weighted |
| 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 shortest path length between source and all other reachable nodes for a weighted graph. |
| all_pairs_dijkstra_path(G) | Compute shortest paths between all nodes in a weighted graph. |
| all_pairs_dijkstra_path_length(G) | 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 |