Skip to main content
`Ctrl`+`K`

# 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 simple paths in the graph.
`all_pairs_all_shortest_paths`(G[, weight, method]) | Compute all shortest paths between all nodes.
`single_source_all_shortest_paths`(G, source) | Compute all shortest simple paths from the given source in the graph.
`shortest_path_length`(G[, source, target, ...]) | Compute shortest path lengths in the graph.
`average_shortest_path_length`(G[, weight, method]) | Returns the average shortest path length.
`has_path`(G, source, target) | Returns 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) | Returns 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 weighted 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, heuristic]) | Returns True if there exists a negative edge cycle anywhere in G.
`find_negative_cycle`(G, source[, weight]) | Returns a cycle with negative total weight if it exists.
`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, ...]) | Returns a list of nodes in a shortest path between source and target using the A* ("A-star") algorithm.
`astar_path_length`(G, source, target[, ...]) | Returns the length of the shortest path between source and target using the A* ("A-star") algorithm.