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

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