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[, …])	Compute all shortest paths in the graph.
shortest_path_length(G[, source, target, …])	Compute shortest path lengths in the graph.
average_shortest_path_length(G[, weight, method])	Return the average shortest path length.
has_path(G, source, target)	Return True if G has a path from source to target.

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.
single_target_shortest_path(G, target[, cutoff])	Compute shortest path to target from all nodes that reach target.
single_target_shortest_path_length(G, target)	Compute the shortest path lengths to target from all reachable nodes.
bidirectional_shortest_path(G, source, target)	Return a list of nodes in a shortest path between source and target.
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 dict of predecessors for the path from source to all nodes in G

Shortest path algorithms for weighed graphs.

dijkstra_predecessor_and_distance(G, source)	Compute weighted shortest path length and predecessors.
dijkstra_path(G, source, target[, weight])	Returns the shortest weighted path from source to target in G.
dijkstra_path_length(G, source, target[, weight])	Returns the shortest weighted path length in G from source to target.
single_source_dijkstra(G, source[, target, …])	Find shortest weighted paths and lengths from a source node.
single_source_dijkstra_path(G, source[, …])	Find shortest weighted paths in G from a source node.
single_source_dijkstra_path_length(G, source)	Find shortest weighted path lengths in G from a source node.
multi_source_dijkstra(G, sources[, target, …])	Find shortest weighted paths and lengths from a given set of source nodes.
multi_source_dijkstra_path(G, sources[, …])	Find shortest weighted paths in G from a given set of source nodes.
multi_source_dijkstra_path_length(G, sources)	Find shortest weighted path lengths in G from a given set of source nodes.
all_pairs_dijkstra(G[, cutoff, weight])	Find shortest weighted paths and lengths between all nodes.
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.
bidirectional_dijkstra(G, source, target[, …])	Dijkstra’s algorithm for shortest paths using bidirectional search.
bellman_ford_path(G, source, target[, weight])	Returns the shortest path from source to target in a weighted graph G.
bellman_ford_path_length(G, source, target)	Returns the shortest path length from source to target in a weighted graph.
single_source_bellman_ford(G, source[, …])	Compute shortest paths and lengths in a weighted graph G.
single_source_bellman_ford_path(G, source[, …])	Compute shortest path between source and all other reachable nodes for a weighted graph.
single_source_bellman_ford_path_length(G, source)	Compute the shortest path length between source and all other reachable nodes for a weighted graph.
all_pairs_bellman_ford_path(G[, weight])	Compute shortest paths between all nodes in a weighted graph.
all_pairs_bellman_ford_path_length(G[, weight])	Compute shortest path lengths between all nodes in a weighted graph.
bellman_ford_predecessor_and_distance(G, source)	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.
goldberg_radzik(G, source[, weight])	Compute shortest path lengths and predecessors on shortest paths in weighted graphs.
johnson(G[, weight])	Uses Johnson’s Algorithm to compute shortest paths.

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.
reconstruct_path(source, target, predecessors)	Reconstruct a path from source to target using the predecessors dict as returned by floyd_warshall_predecessor_and_distance

A* Algorithm

Shortest paths and path lengths using the 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.