Skip to main content
`Ctrl`+`K`

# shortest_simple_paths

shortest_simple_paths(G, source, target, weight=None)
  Generate all simple paths in the graph G from source to target,

    starting from shortest ones.

  A simple path is a path with no repeated nodes.

  If a weighted shortest path search is to be used, no negative weights are allowed.

  Parameters:
    G NetworkX graph
    source node

      Starting node for path

    target node

      Ending node for path

    weight string or function

      If it is a string, it is the name of the edge attribute to be used as a weight.

      If it is a function, the weight of an edge is the value returned by the function. The function must accept exactly three positional arguments: the two endpoints of an edge and the dictionary of edge attributes for that edge. The function must return a number or None. The weight function can be used to hide edges by returning None. So `weight = lambda u, v, d: 1 if d['color']=="red" else None` will find the shortest red path.

      If None all edges are considered to have unit weight. Default value None.

  Returns:
    path_generator: generator

      A generator that produces lists of simple paths, in order from shortest to longest.

  Raises:
    NetworkXNoPath

      If no path exists between source and target.

    NetworkXError

      If source or target nodes are not in the input graph.

    NetworkXNotImplemented

      If the input graph is a Multi[Di]Graph.

  See also

  `all_shortest_paths`
  `shortest_path`
  `all_simple_paths`

  Notes

  This procedure is based on algorithm by Jin Y. Yen [1]. Finding the first \(K\) paths requires \(O(KN^3)\) operations.

  References

  [1]

  Jin Y. Yen, “Finding the K Shortest Loopless Paths in a Network”, Management Science, Vol. 17, No. 11, Theory Series (Jul., 1971), pp. 712-716.

  Examples

      >>> G = nx.cycle_graph(7)
      >>> paths = list(nx.shortest_simple_paths(G, 0, 3))
      >>> print(paths)
      [[0, 1, 2, 3], [0, 6, 5, 4, 3]]

  You can use this function to efficiently compute the k shortest/best paths between two nodes.

      >>> from itertools import islice
      >>> def k_shortest_paths(G, source, target, k, weight=None):
      ...     return list(
      ...         islice(nx.shortest_simple_paths(G, source, target, weight=weight), k)
      ...     )
      >>> for path in k_shortest_paths(G, 0, 3, 2):
      ...     print(path)
      [0, 1, 2, 3]
      [0, 6, 5, 4, 3]