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])	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.