NetworkX

Table Of Contents

Previous topic

networkx.symmetric_difference

Next topic

networkx.shortest_path

Shortest Paths

Compute the shortest paths and path lengths between nodes in the graph.

These algorithms work with undirected and directed graphs.

For directed graphs the paths can be computed in the reverse order by first flipping the edge orientation using R=G.reverse(copy=False).

shortest_path(G[, source, target, weighted]) Compute shortest paths in the graph.
shortest_path_length(G[, source, target, ...]) Compute shortest path lengths in the graph.
average_shortest_path_length(G[, weighted]) Return the average shortest path length.

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]) Compute the shortest path lengths between all nodes in G.
predecessor(G, source[, target, cutoff, ...]) Returns dictionary of predecessors for the path from source to all
floyd_warshall(G) The Floyd-Warshall algorithm for all pairs shortest paths.

Shortest path algorithms for weighed graphs.

dijkstra_path(G, source, target[, weight]) Returns the shortest path from source to target in a weighted
dijkstra_path_length(G, source, target[, weight]) Returns the shortest path length from source to target in a weighted
single_source_dijkstra_path(G, source[, weight]) Compute shortest path between source and all other reachable nodes for a weighted graph.
single_source_dijkstra_path_length(G, source) Compute shortest path length between source and all other reachable nodes for a weighted graph.
all_pairs_dijkstra_path(G[, weight]) Compute shortest paths between all nodes in a weighted graph.
all_pairs_dijkstra_path_length(G[, weight]) Compute shortest path lengths between all nodes in a weighted graph.
single_source_dijkstra(G, source[, target, ...]) Compute shortest paths and lengths in a weighted graph G.
bidirectional_dijkstra(G, source, target[, ...]) Dijkstra’s algorithm for shortest paths using bidirectional search.
bidirectional_shortest_path(G, source, target) Return a list of nodes in a shortest path between source and target.
dijkstra_predecessor_and_distance(G, source) Compute shorest path length and predecessors on shortest paths in weighted graphs.

A* Algorithm

Shortest paths and path lengths using A* (“A star”) algorithm.

astar_path(G, source, target[, heuristic]) Return a list of nodes in a shortest path between source and target
astar_path_length(G, source, target[, heuristic]) Return a list of nodes in a shortest path between source and target