Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# 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, False otherwise. |

## 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 nodes in G. |

Shortest path algorithms for weighed graphs.

dijkstra_path(G, source, target[, weight]) |
Returns the shortest path from source to target in a weighted graph G. |

dijkstra_path_length(G, source, target[, weight]) |
Returns the shortest path length from source to target in a weighted graph. |

single_source_dijkstra_path(G, source[, ...]) |
Compute shortest path between source and all other reachable nodes for a weighted graph. |

single_source_dijkstra_path_length(G, source) |
Compute the shortest path length between source and all other reachable nodes for a weighted graph. |

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

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

dijkstra_predecessor_and_distance(G, source) |
Compute shortest path length and predecessors on shortest paths in weighted graphs. |

bellman_ford(G, source[, weight]) |
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. |

## 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 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[, ...]) |
Return the length of the shortest path between source and target using |