Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Compute the shortest paths and path lengths between nodes in the graph.
4These algorithms work with undirected and directed graphs.
6"""
8import networkx as nx
10__all__ = [
11 "shortest_path",
12 "all_shortest_paths",
13 "single_source_all_shortest_paths",
14 "all_pairs_all_shortest_paths",
15 "shortest_path_length",
16 "average_shortest_path_length",
17 "has_path",
18]
21@nx._dispatchable
22def has_path(G, source, target):
23 """Returns *True* if *G* has a path from *source* to *target*.
25 Parameters
26 ----------
27 G : NetworkX graph
29 source : node
30 Starting node for path
32 target : node
33 Ending node for path
34 """
35 try:
36 nx.shortest_path(G, source, target)
37 except nx.NetworkXNoPath:
38 return False
39 return True
42@nx._dispatchable(edge_attrs="weight")
43def shortest_path(G, source=None, target=None, weight=None, method="dijkstra"):
44 """Compute shortest paths in the graph.
46 Parameters
47 ----------
48 G : NetworkX graph
50 source : node, optional
51 Starting node for path. If not specified, compute shortest
52 paths for each possible starting node.
54 target : node, optional
55 Ending node for path. If not specified, compute shortest
56 paths to all possible nodes.
58 weight : None, string or function, optional (default = None)
59 If None, every edge has weight/distance/cost 1.
60 If a string, use this edge attribute as the edge weight.
61 Any edge attribute not present defaults to 1.
62 If this is a function, the weight of an edge is the value
63 returned by the function. The function must accept exactly
64 three positional arguments: the two endpoints of an edge and
65 the dictionary of edge attributes for that edge.
66 The function must return a number.
68 method : string, optional (default = 'dijkstra')
69 The algorithm to use to compute the path.
70 Supported options: 'dijkstra', 'bellman-ford'.
71 Other inputs produce a ValueError.
72 If `weight` is None, unweighted graph methods are used, and this
73 suggestion is ignored.
75 Returns
76 -------
77 path: list or dictionary or iterator
78 All returned paths include both the source and target in the path.
80 If the source and target are both specified, return a single list
81 of nodes in a shortest path from the source to the target.
83 If only the source is specified, return a dictionary keyed by
84 targets with a list of nodes in a shortest path from the source
85 to one of the targets.
87 If only the target is specified, return a dictionary keyed by
88 sources with a list of nodes in a shortest path from one of the
89 sources to the target.
91 If neither the source nor target are specified, return an iterator
92 over (source, dictionary) where dictionary is keyed by target to
93 list of nodes in a shortest path from the source to the target.
95 Raises
96 ------
97 NodeNotFound
98 If `source` is not in `G`.
100 ValueError
101 If `method` is not among the supported options.
103 NetworkXNoPath
104 If `source` and `target` are specified but no path exists between them.
106 Examples
107 --------
108 >>> G = nx.path_graph(5)
109 >>> print(nx.shortest_path(G, source=0, target=4))
110 [0, 1, 2, 3, 4]
111 >>> p = nx.shortest_path(G, source=0) # target not specified
112 >>> p[3] # shortest path from source=0 to target=3
113 [0, 1, 2, 3]
114 >>> p = nx.shortest_path(G, target=4) # source not specified
115 >>> p[1] # shortest path from source=1 to target=4
116 [1, 2, 3, 4]
117 >>> p = dict(nx.shortest_path(G)) # source, target not specified
118 >>> p[2][4] # shortest path from source=2 to target=4
119 [2, 3, 4]
121 Notes
122 -----
123 There may be more than one shortest path between a source and target.
124 This returns only one of them.
126 See Also
127 --------
128 all_pairs_shortest_path
129 all_pairs_dijkstra_path
130 all_pairs_bellman_ford_path
131 single_source_shortest_path
132 single_source_dijkstra_path
133 single_source_bellman_ford_path
134 """
135 if method not in ("dijkstra", "bellman-ford"):
136 # so we don't need to check in each branch later
137 raise ValueError(f"method not supported: {method}")
138 method = "unweighted" if weight is None else method
139 if source is None:
140 if target is None:
141 # Find paths between all pairs. Iterator of dicts.
142 if method == "unweighted":
143 paths = nx.all_pairs_shortest_path(G)
144 elif method == "dijkstra":
145 paths = nx.all_pairs_dijkstra_path(G, weight=weight)
146 else: # method == 'bellman-ford':
147 paths = nx.all_pairs_bellman_ford_path(G, weight=weight)
148 else:
149 # Find paths from all nodes co-accessible to the target.
150 if G.is_directed():
151 G = G.reverse(copy=False)
152 if method == "unweighted":
153 paths = nx.single_source_shortest_path(G, target)
154 elif method == "dijkstra":
155 paths = nx.single_source_dijkstra_path(G, target, weight=weight)
156 else: # method == 'bellman-ford':
157 paths = nx.single_source_bellman_ford_path(G, target, weight=weight)
158 # Now flip the paths so they go from a source to the target.
159 for target in paths:
160 paths[target] = list(reversed(paths[target]))
161 else:
162 if target is None:
163 # Find paths to all nodes accessible from the source.
164 if method == "unweighted":
165 paths = nx.single_source_shortest_path(G, source)
166 elif method == "dijkstra":
167 paths = nx.single_source_dijkstra_path(G, source, weight=weight)
168 else: # method == 'bellman-ford':
169 paths = nx.single_source_bellman_ford_path(G, source, weight=weight)
170 else:
171 # Find shortest source-target path.
172 if method == "unweighted":
173 paths = nx.bidirectional_shortest_path(G, source, target)
174 elif method == "dijkstra":
175 _, paths = nx.bidirectional_dijkstra(G, source, target, weight)
176 else: # method == 'bellman-ford':
177 paths = nx.bellman_ford_path(G, source, target, weight)
178 return paths
181@nx._dispatchable(edge_attrs="weight")
182def shortest_path_length(G, source=None, target=None, weight=None, method="dijkstra"):
183 """Compute shortest path lengths in the graph.
185 Parameters
186 ----------
187 G : NetworkX graph
189 source : node, optional
190 Starting node for path.
191 If not specified, compute shortest path lengths using all nodes as
192 source nodes.
194 target : node, optional
195 Ending node for path.
196 If not specified, compute shortest path lengths using all nodes as
197 target nodes.
199 weight : None, string or function, optional (default = None)
200 If None, every edge has weight/distance/cost 1.
201 If a string, use this edge attribute as the edge weight.
202 Any edge attribute not present defaults to 1.
203 If this is a function, the weight of an edge is the value
204 returned by the function. The function must accept exactly
205 three positional arguments: the two endpoints of an edge and
206 the dictionary of edge attributes for that edge.
207 The function must return a number.
209 method : string, optional (default = 'dijkstra')
210 The algorithm to use to compute the path length.
211 Supported options: 'dijkstra', 'bellman-ford'.
212 Other inputs produce a ValueError.
213 If `weight` is None, unweighted graph methods are used, and this
214 suggestion is ignored.
216 Returns
217 -------
218 length: number or iterator
219 If the source and target are both specified, return the length of
220 the shortest path from the source to the target.
222 If only the source is specified, return a dict keyed by target
223 to the shortest path length from the source to that target.
225 If only the target is specified, return a dict keyed by source
226 to the shortest path length from that source to the target.
228 If neither the source nor target are specified, return an iterator
229 over (source, dictionary) where dictionary is keyed by target to
230 shortest path length from source to that target.
232 Raises
233 ------
234 NodeNotFound
235 If `source` is not in `G`.
237 NetworkXNoPath
238 If no path exists between source and target.
240 ValueError
241 If `method` is not among the supported options.
243 Examples
244 --------
245 >>> G = nx.path_graph(5)
246 >>> nx.shortest_path_length(G, source=0, target=4)
247 4
248 >>> p = nx.shortest_path_length(G, source=0) # target not specified
249 >>> p[4]
250 4
251 >>> p = nx.shortest_path_length(G, target=4) # source not specified
252 >>> p[0]
253 4
254 >>> p = dict(nx.shortest_path_length(G)) # source,target not specified
255 >>> p[0][4]
256 4
258 Notes
259 -----
260 The length of the path is always 1 less than the number of nodes involved
261 in the path since the length measures the number of edges followed.
263 For digraphs this returns the shortest directed path length. To find path
264 lengths in the reverse direction use G.reverse(copy=False) first to flip
265 the edge orientation.
267 See Also
268 --------
269 all_pairs_shortest_path_length
270 all_pairs_dijkstra_path_length
271 all_pairs_bellman_ford_path_length
272 single_source_shortest_path_length
273 single_source_dijkstra_path_length
274 single_source_bellman_ford_path_length
275 """
276 if method not in ("dijkstra", "bellman-ford"):
277 # so we don't need to check in each branch later
278 raise ValueError(f"method not supported: {method}")
279 method = "unweighted" if weight is None else method
280 if source is None:
281 if target is None:
282 # Find paths between all pairs.
283 if method == "unweighted":
284 paths = nx.all_pairs_shortest_path_length(G)
285 elif method == "dijkstra":
286 paths = nx.all_pairs_dijkstra_path_length(G, weight=weight)
287 else: # method == 'bellman-ford':
288 paths = nx.all_pairs_bellman_ford_path_length(G, weight=weight)
289 else:
290 # Find paths from all nodes co-accessible to the target.
291 if G.is_directed():
292 G = G.reverse(copy=False)
293 if method == "unweighted":
294 path_length = nx.single_source_shortest_path_length
295 paths = path_length(G, target)
296 elif method == "dijkstra":
297 path_length = nx.single_source_dijkstra_path_length
298 paths = path_length(G, target, weight=weight)
299 else: # method == 'bellman-ford':
300 path_length = nx.single_source_bellman_ford_path_length
301 paths = path_length(G, target, weight=weight)
302 else:
303 if target is None:
304 # Find paths to all nodes accessible from the source.
305 if method == "unweighted":
306 paths = nx.single_source_shortest_path_length(G, source)
307 elif method == "dijkstra":
308 path_length = nx.single_source_dijkstra_path_length
309 paths = path_length(G, source, weight=weight)
310 else: # method == 'bellman-ford':
311 path_length = nx.single_source_bellman_ford_path_length
312 paths = path_length(G, source, weight=weight)
313 else:
314 # Find shortest source-target path.
315 if method == "unweighted":
316 p = nx.bidirectional_shortest_path(G, source, target)
317 paths = len(p) - 1
318 elif method == "dijkstra":
319 paths = nx.dijkstra_path_length(G, source, target, weight)
320 else: # method == 'bellman-ford':
321 paths = nx.bellman_ford_path_length(G, source, target, weight)
322 return paths
325@nx._dispatchable(edge_attrs="weight")
326def average_shortest_path_length(G, weight=None, method=None):
327 r"""Returns the average shortest path length.
329 The average shortest path length is
331 .. math::
333 a =\sum_{\substack{s,t \in V \\ s\neq t}} \frac{d(s, t)}{n(n-1)}
335 where `V` is the set of nodes in `G`,
336 `d(s, t)` is the shortest path from `s` to `t`,
337 and `n` is the number of nodes in `G`.
339 .. versionchanged:: 3.0
340 An exception is raised for directed graphs that are not strongly
341 connected.
343 Parameters
344 ----------
345 G : NetworkX graph
347 weight : None, string or function, optional (default = None)
348 If None, every edge has weight/distance/cost 1.
349 If a string, use this edge attribute as the edge weight.
350 Any edge attribute not present defaults to 1.
351 If this is a function, the weight of an edge is the value
352 returned by the function. The function must accept exactly
353 three positional arguments: the two endpoints of an edge and
354 the dictionary of edge attributes for that edge.
355 The function must return a number.
357 method : string, optional (default = 'unweighted' or 'dijkstra')
358 The algorithm to use to compute the path lengths.
359 Supported options are 'unweighted', 'dijkstra', 'bellman-ford',
360 'floyd-warshall' and 'floyd-warshall-numpy'.
361 Other method values produce a ValueError.
362 The default method is 'unweighted' if `weight` is None,
363 otherwise the default method is 'dijkstra'.
365 Raises
366 ------
367 NetworkXPointlessConcept
368 If `G` is the null graph (that is, the graph on zero nodes).
370 NetworkXError
371 If `G` is not connected (or not strongly connected, in the case
372 of a directed graph).
374 ValueError
375 If `method` is not among the supported options.
377 Examples
378 --------
379 >>> G = nx.path_graph(5)
380 >>> nx.average_shortest_path_length(G)
381 2.0
383 For disconnected graphs, you can compute the average shortest path
384 length for each component
386 >>> G = nx.Graph([(1, 2), (3, 4)])
387 >>> for C in (G.subgraph(c).copy() for c in nx.connected_components(G)):
388 ... print(nx.average_shortest_path_length(C))
389 1.0
390 1.0
392 """
393 single_source_methods = ["unweighted", "dijkstra", "bellman-ford"]
394 all_pairs_methods = ["floyd-warshall", "floyd-warshall-numpy"]
395 supported_methods = single_source_methods + all_pairs_methods
397 if method is None:
398 method = "unweighted" if weight is None else "dijkstra"
399 if method not in supported_methods:
400 raise ValueError(f"method not supported: {method}")
402 n = len(G)
403 # For the special case of the null graph, raise an exception, since
404 # there are no paths in the null graph.
405 if n == 0:
406 msg = (
407 "the null graph has no paths, thus there is no average shortest path length"
408 )
409 raise nx.NetworkXPointlessConcept(msg)
410 # For the special case of the trivial graph, return zero immediately.
411 if n == 1:
412 return 0
413 # Shortest path length is undefined if the graph is not strongly connected.
414 if G.is_directed() and not nx.is_strongly_connected(G):
415 raise nx.NetworkXError("Graph is not strongly connected.")
416 # Shortest path length is undefined if the graph is not connected.
417 if not G.is_directed() and not nx.is_connected(G):
418 raise nx.NetworkXError("Graph is not connected.")
420 # Compute all-pairs shortest paths.
421 def path_length(v):
422 if method == "unweighted":
423 return nx.single_source_shortest_path_length(G, v)
424 elif method == "dijkstra":
425 return nx.single_source_dijkstra_path_length(G, v, weight=weight)
426 elif method == "bellman-ford":
427 return nx.single_source_bellman_ford_path_length(G, v, weight=weight)
429 if method in single_source_methods:
430 # Sum the distances for each (ordered) pair of source and target node.
431 s = sum(l for u in G for l in path_length(u).values())
432 else:
433 if method == "floyd-warshall":
434 all_pairs = nx.floyd_warshall(G, weight=weight)
435 s = sum(sum(t.values()) for t in all_pairs.values())
436 elif method == "floyd-warshall-numpy":
437 s = float(nx.floyd_warshall_numpy(G, weight=weight).sum())
438 return s / (n * (n - 1))
441@nx._dispatchable(edge_attrs="weight")
442def all_shortest_paths(G, source, target, weight=None, method="dijkstra"):
443 """Compute all shortest simple paths in the graph.
445 Parameters
446 ----------
447 G : NetworkX graph
449 source : node
450 Starting node for path.
452 target : node
453 Ending node for path.
455 weight : None, string or function, optional (default = None)
456 If None, every edge has weight/distance/cost 1.
457 If a string, use this edge attribute as the edge weight.
458 Any edge attribute not present defaults to 1.
459 If this is a function, the weight of an edge is the value
460 returned by the function. The function must accept exactly
461 three positional arguments: the two endpoints of an edge and
462 the dictionary of edge attributes for that edge.
463 The function must return a number.
465 method : string, optional (default = 'dijkstra')
466 The algorithm to use to compute the path lengths.
467 Supported options: 'dijkstra', 'bellman-ford'.
468 Other inputs produce a ValueError.
469 If `weight` is None, unweighted graph methods are used, and this
470 suggestion is ignored.
472 Returns
473 -------
474 paths : generator of lists
475 A generator of all paths between source and target.
477 Raises
478 ------
479 ValueError
480 If `method` is not among the supported options.
482 NetworkXNoPath
483 If `target` cannot be reached from `source`.
485 Examples
486 --------
487 >>> G = nx.Graph()
488 >>> nx.add_path(G, [0, 1, 2])
489 >>> nx.add_path(G, [0, 10, 2])
490 >>> print([p for p in nx.all_shortest_paths(G, source=0, target=2)])
491 [[0, 1, 2], [0, 10, 2]]
493 Notes
494 -----
495 There may be many shortest paths between the source and target. If G
496 contains zero-weight cycles, this function will not produce all shortest
497 paths because doing so would produce infinitely many paths of unbounded
498 length -- instead, we only produce the shortest simple paths.
500 See Also
501 --------
502 shortest_path
503 single_source_shortest_path
504 all_pairs_shortest_path
505 """
506 method = "unweighted" if weight is None else method
507 if method == "unweighted":
508 pred = nx.predecessor(G, source)
509 elif method == "dijkstra":
510 pred, dist = nx.dijkstra_predecessor_and_distance(G, source, weight=weight)
511 elif method == "bellman-ford":
512 pred, dist = nx.bellman_ford_predecessor_and_distance(G, source, weight=weight)
513 else:
514 raise ValueError(f"method not supported: {method}")
516 return _build_paths_from_predecessors({source}, target, pred)
519@nx._dispatchable(edge_attrs="weight")
520def single_source_all_shortest_paths(G, source, weight=None, method="dijkstra"):
521 """Compute all shortest simple paths from the given source in the graph.
523 Parameters
524 ----------
525 G : NetworkX graph
527 source : node
528 Starting node for path.
530 weight : None, string or function, optional (default = None)
531 If None, every edge has weight/distance/cost 1.
532 If a string, use this edge attribute as the edge weight.
533 Any edge attribute not present defaults to 1.
534 If this is a function, the weight of an edge is the value
535 returned by the function. The function must accept exactly
536 three positional arguments: the two endpoints of an edge and
537 the dictionary of edge attributes for that edge.
538 The function must return a number.
540 method : string, optional (default = 'dijkstra')
541 The algorithm to use to compute the path lengths.
542 Supported options: 'dijkstra', 'bellman-ford'.
543 Other inputs produce a ValueError.
544 If `weight` is None, unweighted graph methods are used, and this
545 suggestion is ignored.
547 Returns
548 -------
549 paths : generator of dictionary
550 A generator of all paths between source and all nodes in the graph.
552 Raises
553 ------
554 ValueError
555 If `method` is not among the supported options.
557 Examples
558 --------
559 >>> G = nx.Graph()
560 >>> nx.add_path(G, [0, 1, 2, 3, 0])
561 >>> dict(nx.single_source_all_shortest_paths(G, source=0))
562 {0: [[0]], 1: [[0, 1]], 3: [[0, 3]], 2: [[0, 1, 2], [0, 3, 2]]}
564 Notes
565 -----
566 There may be many shortest paths between the source and target. If G
567 contains zero-weight cycles, this function will not produce all shortest
568 paths because doing so would produce infinitely many paths of unbounded
569 length -- instead, we only produce the shortest simple paths.
571 See Also
572 --------
573 shortest_path
574 all_shortest_paths
575 single_source_shortest_path
576 all_pairs_shortest_path
577 all_pairs_all_shortest_paths
578 """
579 method = "unweighted" if weight is None else method
580 if method == "unweighted":
581 pred = nx.predecessor(G, source)
582 elif method == "dijkstra":
583 pred, dist = nx.dijkstra_predecessor_and_distance(G, source, weight=weight)
584 elif method == "bellman-ford":
585 pred, dist = nx.bellman_ford_predecessor_and_distance(G, source, weight=weight)
586 else:
587 raise ValueError(f"method not supported: {method}")
588 for n in pred:
589 yield n, list(_build_paths_from_predecessors({source}, n, pred))
592@nx._dispatchable(edge_attrs="weight")
593def all_pairs_all_shortest_paths(G, weight=None, method="dijkstra"):
594 """Compute all shortest paths between all nodes.
596 Parameters
597 ----------
598 G : NetworkX graph
600 weight : None, string or function, optional (default = None)
601 If None, every edge has weight/distance/cost 1.
602 If a string, use this edge attribute as the edge weight.
603 Any edge attribute not present defaults to 1.
604 If this is a function, the weight of an edge is the value
605 returned by the function. The function must accept exactly
606 three positional arguments: the two endpoints of an edge and
607 the dictionary of edge attributes for that edge.
608 The function must return a number.
610 method : string, optional (default = 'dijkstra')
611 The algorithm to use to compute the path lengths.
612 Supported options: 'dijkstra', 'bellman-ford'.
613 Other inputs produce a ValueError.
614 If `weight` is None, unweighted graph methods are used, and this
615 suggestion is ignored.
617 Returns
618 -------
619 paths : generator of dictionary
620 Dictionary of arrays, keyed by source and target, of all shortest paths.
622 Raises
623 ------
624 ValueError
625 If `method` is not among the supported options.
627 Examples
628 --------
629 >>> G = nx.cycle_graph(4)
630 >>> dict(nx.all_pairs_all_shortest_paths(G))[0][2]
631 [[0, 1, 2], [0, 3, 2]]
632 >>> dict(nx.all_pairs_all_shortest_paths(G))[0][3]
633 [[0, 3]]
635 Notes
636 -----
637 There may be multiple shortest paths with equal lengths. Unlike
638 all_pairs_shortest_path, this method returns all shortest paths.
640 See Also
641 --------
642 all_pairs_shortest_path
643 single_source_all_shortest_paths
644 """
645 for n in G:
646 yield (
647 n,
648 dict(single_source_all_shortest_paths(G, n, weight=weight, method=method)),
649 )
652def _build_paths_from_predecessors(sources, target, pred):
653 """Compute all simple paths to target, given the predecessors found in
654 pred, terminating when any source in sources is found.
656 Parameters
657 ----------
658 sources : set
659 Starting nodes for path.
661 target : node
662 Ending node for path.
664 pred : dict
665 A dictionary of predecessor lists, keyed by node
667 Returns
668 -------
669 paths : generator of lists
670 A generator of all paths between source and target.
672 Raises
673 ------
674 NetworkXNoPath
675 If `target` cannot be reached from `source`.
677 Notes
678 -----
679 There may be many paths between the sources and target. If there are
680 cycles among the predecessors, this function will not produce all
681 possible paths because doing so would produce infinitely many paths
682 of unbounded length -- instead, we only produce simple paths.
684 See Also
685 --------
686 shortest_path
687 single_source_shortest_path
688 all_pairs_shortest_path
689 all_shortest_paths
690 bellman_ford_path
691 """
692 if target not in pred:
693 raise nx.NetworkXNoPath(f"Target {target} cannot be reached from given sources")
695 seen = {target}
696 stack = [[target, 0]]
697 top = 0
698 while top >= 0:
699 node, i = stack[top]
700 if node in sources:
701 yield [p for p, n in reversed(stack[: top + 1])]
702 if len(pred[node]) > i:
703 stack[top][1] = i + 1
704 next = pred[node][i]
705 if next in seen:
706 continue
707 else:
708 seen.add(next)
709 top += 1
710 if top == len(stack):
711 stack.append([next, 0])
712 else:
713 stack[top][:] = [next, 0]
714 else:
715 seen.discard(node)
716 top -= 1