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.

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.