Warning
This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.
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]) | 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. |
Dense Graphs¶
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. |
A* 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 |