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. |
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 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_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_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_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[, cutoff, weight]) |
Compute shortest paths between all nodes in a weighted graph. |
all_pairs_bellman_ford_path_length (G[, …]) |
Compute shortest path lengths between all nodes in a weighted graph. |
single_source_bellman_ford (G, source[, …]) |
Compute shortest paths and lengths in a weighted graph G. |
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. |
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. |
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. |