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.

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.

## 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 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.