# 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]) |
Computes 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. |

`johnson` (G[, weight]) |
Compute shortest paths between all nodes in a weighted graph using Johnson’s algorithm. |

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