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 Examples
104 --------
105 >>> G = nx.path_graph(5)
106 >>> print(nx.shortest_path(G, source=0, target=4))
107 [0, 1, 2, 3, 4]
108 >>> p = nx.shortest_path(G, source=0) # target not specified
109 >>> p[3] # shortest path from source=0 to target=3
110 [0, 1, 2, 3]
111 >>> p = nx.shortest_path(G, target=4) # source not specified
112 >>> p[1] # shortest path from source=1 to target=4
113 [1, 2, 3, 4]
114 >>> p = dict(nx.shortest_path(G)) # source, target not specified
115 >>> p[2][4] # shortest path from source=2 to target=4
116 [2, 3, 4]
118 Notes
119 -----
120 There may be more than one shortest path between a source and target.
121 This returns only one of them.
123 See Also
124 --------
125 all_pairs_shortest_path
126 all_pairs_dijkstra_path
127 all_pairs_bellman_ford_path
128 single_source_shortest_path
129 single_source_dijkstra_path
130 single_source_bellman_ford_path
131 """
132 if method not in ("dijkstra", "bellman-ford"):
133 # so we don't need to check in each branch later
134 raise ValueError(f"method not supported: {method}")
135 method = "unweighted" if weight is None else method
136 if source is None:
137 if target is None:
138 # Find paths between all pairs. Iterator of dicts.
139 if method == "unweighted":
140 paths = nx.all_pairs_shortest_path(G)
141 elif method == "dijkstra":
142 paths = nx.all_pairs_dijkstra_path(G, weight=weight)
143 else: # method == 'bellman-ford':
144 paths = nx.all_pairs_bellman_ford_path(G, weight=weight)
145 else:
146 # Find paths from all nodes co-accessible to the target.
147 if G.is_directed():
148 G = G.reverse(copy=False)
149 if method == "unweighted":
150 paths = nx.single_source_shortest_path(G, target)
151 elif method == "dijkstra":
152 paths = nx.single_source_dijkstra_path(G, target, weight=weight)
153 else: # method == 'bellman-ford':
154 paths = nx.single_source_bellman_ford_path(G, target, weight=weight)
155 # Now flip the paths so they go from a source to the target.
156 for target in paths:
157 paths[target] = list(reversed(paths[target]))
158 else:
159 if target is None:
160 # Find paths to all nodes accessible from the source.
161 if method == "unweighted":
162 paths = nx.single_source_shortest_path(G, source)
163 elif method == "dijkstra":
164 paths = nx.single_source_dijkstra_path(G, source, weight=weight)
165 else: # method == 'bellman-ford':
166 paths = nx.single_source_bellman_ford_path(G, source, weight=weight)
167 else:
168 # Find shortest source-target path.
169 if method == "unweighted":
170 paths = nx.bidirectional_shortest_path(G, source, target)
171 elif method == "dijkstra":
172 _, paths = nx.bidirectional_dijkstra(G, source, target, weight)
173 else: # method == 'bellman-ford':
174 paths = nx.bellman_ford_path(G, source, target, weight)
175 return paths
178@nx._dispatchable(edge_attrs="weight")
179def shortest_path_length(G, source=None, target=None, weight=None, method="dijkstra"):
180 """Compute shortest path lengths in the graph.
182 Parameters
183 ----------
184 G : NetworkX graph
186 source : node, optional
187 Starting node for path.
188 If not specified, compute shortest path lengths using all nodes as
189 source nodes.
191 target : node, optional
192 Ending node for path.
193 If not specified, compute shortest path lengths using all nodes as
194 target nodes.
196 weight : None, string or function, optional (default = None)
197 If None, every edge has weight/distance/cost 1.
198 If a string, use this edge attribute as the edge weight.
199 Any edge attribute not present defaults to 1.
200 If this is a function, the weight of an edge is the value
201 returned by the function. The function must accept exactly
202 three positional arguments: the two endpoints of an edge and
203 the dictionary of edge attributes for that edge.
204 The function must return a number.
206 method : string, optional (default = 'dijkstra')
207 The algorithm to use to compute the path length.
208 Supported options: 'dijkstra', 'bellman-ford'.
209 Other inputs produce a ValueError.
210 If `weight` is None, unweighted graph methods are used, and this
211 suggestion is ignored.
213 Returns
214 -------
215 length: number or iterator
216 If the source and target are both specified, return the length of
217 the shortest path from the source to the target.
219 If only the source is specified, return a dict keyed by target
220 to the shortest path length from the source to that target.
222 If only the target is specified, return a dict keyed by source
223 to the shortest path length from that source to the target.
225 If neither the source nor target are specified, return an iterator
226 over (source, dictionary) where dictionary is keyed by target to
227 shortest path length from source to that target.
229 Raises
230 ------
231 NodeNotFound
232 If `source` is not in `G`.
234 NetworkXNoPath
235 If no path exists between source and target.
237 ValueError
238 If `method` is not among the supported options.
240 Examples
241 --------
242 >>> G = nx.path_graph(5)
243 >>> nx.shortest_path_length(G, source=0, target=4)
244 4
245 >>> p = nx.shortest_path_length(G, source=0) # target not specified
246 >>> p[4]
247 4
248 >>> p = nx.shortest_path_length(G, target=4) # source not specified
249 >>> p[0]
250 4
251 >>> p = dict(nx.shortest_path_length(G)) # source,target not specified
252 >>> p[0][4]
253 4
255 Notes
256 -----
257 The length of the path is always 1 less than the number of nodes involved
258 in the path since the length measures the number of edges followed.
260 For digraphs this returns the shortest directed path length. To find path
261 lengths in the reverse direction use G.reverse(copy=False) first to flip
262 the edge orientation.
264 See Also
265 --------
266 all_pairs_shortest_path_length
267 all_pairs_dijkstra_path_length
268 all_pairs_bellman_ford_path_length
269 single_source_shortest_path_length
270 single_source_dijkstra_path_length
271 single_source_bellman_ford_path_length
272 """
273 if method not in ("dijkstra", "bellman-ford"):
274 # so we don't need to check in each branch later
275 raise ValueError(f"method not supported: {method}")
276 method = "unweighted" if weight is None else method
277 if source is None:
278 if target is None:
279 # Find paths between all pairs.
280 if method == "unweighted":
281 paths = nx.all_pairs_shortest_path_length(G)
282 elif method == "dijkstra":
283 paths = nx.all_pairs_dijkstra_path_length(G, weight=weight)
284 else: # method == 'bellman-ford':
285 paths = nx.all_pairs_bellman_ford_path_length(G, weight=weight)
286 else:
287 # Find paths from all nodes co-accessible to the target.
288 if G.is_directed():
289 G = G.reverse(copy=False)
290 if method == "unweighted":
291 path_length = nx.single_source_shortest_path_length
292 paths = path_length(G, target)
293 elif method == "dijkstra":
294 path_length = nx.single_source_dijkstra_path_length
295 paths = path_length(G, target, weight=weight)
296 else: # method == 'bellman-ford':
297 path_length = nx.single_source_bellman_ford_path_length
298 paths = path_length(G, target, weight=weight)
299 else:
300 if target is None:
301 # Find paths to all nodes accessible from the source.
302 if method == "unweighted":
303 paths = nx.single_source_shortest_path_length(G, source)
304 elif method == "dijkstra":
305 path_length = nx.single_source_dijkstra_path_length
306 paths = path_length(G, source, weight=weight)
307 else: # method == 'bellman-ford':
308 path_length = nx.single_source_bellman_ford_path_length
309 paths = path_length(G, source, weight=weight)
310 else:
311 # Find shortest source-target path.
312 if method == "unweighted":
313 p = nx.bidirectional_shortest_path(G, source, target)
314 paths = len(p) - 1
315 elif method == "dijkstra":
316 paths = nx.dijkstra_path_length(G, source, target, weight)
317 else: # method == 'bellman-ford':
318 paths = nx.bellman_ford_path_length(G, source, target, weight)
319 return paths
322@nx._dispatchable(edge_attrs="weight")
323def average_shortest_path_length(G, weight=None, method=None):
324 r"""Returns the average shortest path length.
326 The average shortest path length is
328 .. math::
330 a =\sum_{\substack{s,t \in V \\ s\neq t}} \frac{d(s, t)}{n(n-1)}
332 where `V` is the set of nodes in `G`,
333 `d(s, t)` is the shortest path from `s` to `t`,
334 and `n` is the number of nodes in `G`.
336 .. versionchanged:: 3.0
337 An exception is raised for directed graphs that are not strongly
338 connected.
340 Parameters
341 ----------
342 G : NetworkX graph
344 weight : None, string or function, optional (default = None)
345 If None, every edge has weight/distance/cost 1.
346 If a string, use this edge attribute as the edge weight.
347 Any edge attribute not present defaults to 1.
348 If this is a function, the weight of an edge is the value
349 returned by the function. The function must accept exactly
350 three positional arguments: the two endpoints of an edge and
351 the dictionary of edge attributes for that edge.
352 The function must return a number.
354 method : string, optional (default = 'unweighted' or 'dijkstra')
355 The algorithm to use to compute the path lengths.
356 Supported options are 'unweighted', 'dijkstra', 'bellman-ford',
357 'floyd-warshall' and 'floyd-warshall-numpy'.
358 Other method values produce a ValueError.
359 The default method is 'unweighted' if `weight` is None,
360 otherwise the default method is 'dijkstra'.
362 Raises
363 ------
364 NetworkXPointlessConcept
365 If `G` is the null graph (that is, the graph on zero nodes).
367 NetworkXError
368 If `G` is not connected (or not strongly connected, in the case
369 of a directed graph).
371 ValueError
372 If `method` is not among the supported options.
374 Examples
375 --------
376 >>> G = nx.path_graph(5)
377 >>> nx.average_shortest_path_length(G)
378 2.0
380 For disconnected graphs, you can compute the average shortest path
381 length for each component
383 >>> G = nx.Graph([(1, 2), (3, 4)])
384 >>> for C in (G.subgraph(c).copy() for c in nx.connected_components(G)):
385 ... print(nx.average_shortest_path_length(C))
386 1.0
387 1.0
389 """
390 single_source_methods = ["unweighted", "dijkstra", "bellman-ford"]
391 all_pairs_methods = ["floyd-warshall", "floyd-warshall-numpy"]
392 supported_methods = single_source_methods + all_pairs_methods
394 if method is None:
395 method = "unweighted" if weight is None else "dijkstra"
396 if method not in supported_methods:
397 raise ValueError(f"method not supported: {method}")
399 n = len(G)
400 # For the special case of the null graph, raise an exception, since
401 # there are no paths in the null graph.
402 if n == 0:
403 msg = (
404 "the null graph has no paths, thus there is no average shortest path length"
405 )
406 raise nx.NetworkXPointlessConcept(msg)
407 # For the special case of the trivial graph, return zero immediately.
408 if n == 1:
409 return 0
410 # Shortest path length is undefined if the graph is not strongly connected.
411 if G.is_directed() and not nx.is_strongly_connected(G):
412 raise nx.NetworkXError("Graph is not strongly connected.")
413 # Shortest path length is undefined if the graph is not connected.
414 if not G.is_directed() and not nx.is_connected(G):
415 raise nx.NetworkXError("Graph is not connected.")
417 # Compute all-pairs shortest paths.
418 def path_length(v):
419 if method == "unweighted":
420 return nx.single_source_shortest_path_length(G, v)
421 elif method == "dijkstra":
422 return nx.single_source_dijkstra_path_length(G, v, weight=weight)
423 elif method == "bellman-ford":
424 return nx.single_source_bellman_ford_path_length(G, v, weight=weight)
426 if method in single_source_methods:
427 # Sum the distances for each (ordered) pair of source and target node.
428 s = sum(l for u in G for l in path_length(u).values())
429 else:
430 if method == "floyd-warshall":
431 all_pairs = nx.floyd_warshall(G, weight=weight)
432 s = sum(sum(t.values()) for t in all_pairs.values())
433 elif method == "floyd-warshall-numpy":
434 s = float(nx.floyd_warshall_numpy(G, weight=weight).sum())
435 return s / (n * (n - 1))
438@nx._dispatchable(edge_attrs="weight")
439def all_shortest_paths(G, source, target, weight=None, method="dijkstra"):
440 """Compute all shortest simple paths in the graph.
442 Parameters
443 ----------
444 G : NetworkX graph
446 source : node
447 Starting node for path.
449 target : node
450 Ending node for path.
452 weight : None, string or function, optional (default = None)
453 If None, every edge has weight/distance/cost 1.
454 If a string, use this edge attribute as the edge weight.
455 Any edge attribute not present defaults to 1.
456 If this is a function, the weight of an edge is the value
457 returned by the function. The function must accept exactly
458 three positional arguments: the two endpoints of an edge and
459 the dictionary of edge attributes for that edge.
460 The function must return a number.
462 method : string, optional (default = 'dijkstra')
463 The algorithm to use to compute the path lengths.
464 Supported options: 'dijkstra', 'bellman-ford'.
465 Other inputs produce a ValueError.
466 If `weight` is None, unweighted graph methods are used, and this
467 suggestion is ignored.
469 Returns
470 -------
471 paths : generator of lists
472 A generator of all paths between source and target.
474 Raises
475 ------
476 ValueError
477 If `method` is not among the supported options.
479 NetworkXNoPath
480 If `target` cannot be reached from `source`.
482 Examples
483 --------
484 >>> G = nx.Graph()
485 >>> nx.add_path(G, [0, 1, 2])
486 >>> nx.add_path(G, [0, 10, 2])
487 >>> print([p for p in nx.all_shortest_paths(G, source=0, target=2)])
488 [[0, 1, 2], [0, 10, 2]]
490 Notes
491 -----
492 There may be many shortest paths between the source and target. If G
493 contains zero-weight cycles, this function will not produce all shortest
494 paths because doing so would produce infinitely many paths of unbounded
495 length -- instead, we only produce the shortest simple paths.
497 See Also
498 --------
499 shortest_path
500 single_source_shortest_path
501 all_pairs_shortest_path
502 """
503 method = "unweighted" if weight is None else method
504 if method == "unweighted":
505 pred = nx.predecessor(G, source)
506 elif method == "dijkstra":
507 pred, dist = nx.dijkstra_predecessor_and_distance(G, source, weight=weight)
508 elif method == "bellman-ford":
509 pred, dist = nx.bellman_ford_predecessor_and_distance(G, source, weight=weight)
510 else:
511 raise ValueError(f"method not supported: {method}")
513 return _build_paths_from_predecessors({source}, target, pred)
516@nx._dispatchable(edge_attrs="weight")
517def single_source_all_shortest_paths(G, source, weight=None, method="dijkstra"):
518 """Compute all shortest simple paths from the given source in the graph.
520 Parameters
521 ----------
522 G : NetworkX graph
524 source : node
525 Starting node for path.
527 weight : None, string or function, optional (default = None)
528 If None, every edge has weight/distance/cost 1.
529 If a string, use this edge attribute as the edge weight.
530 Any edge attribute not present defaults to 1.
531 If this is a function, the weight of an edge is the value
532 returned by the function. The function must accept exactly
533 three positional arguments: the two endpoints of an edge and
534 the dictionary of edge attributes for that edge.
535 The function must return a number.
537 method : string, optional (default = 'dijkstra')
538 The algorithm to use to compute the path lengths.
539 Supported options: 'dijkstra', 'bellman-ford'.
540 Other inputs produce a ValueError.
541 If `weight` is None, unweighted graph methods are used, and this
542 suggestion is ignored.
544 Returns
545 -------
546 paths : generator of dictionary
547 A generator of all paths between source and all nodes in the graph.
549 Raises
550 ------
551 ValueError
552 If `method` is not among the supported options.
554 Examples
555 --------
556 >>> G = nx.Graph()
557 >>> nx.add_path(G, [0, 1, 2, 3, 0])
558 >>> dict(nx.single_source_all_shortest_paths(G, source=0))
559 {0: [[0]], 1: [[0, 1]], 3: [[0, 3]], 2: [[0, 1, 2], [0, 3, 2]]}
561 Notes
562 -----
563 There may be many shortest paths between the source and target. If G
564 contains zero-weight cycles, this function will not produce all shortest
565 paths because doing so would produce infinitely many paths of unbounded
566 length -- instead, we only produce the shortest simple paths.
568 See Also
569 --------
570 shortest_path
571 all_shortest_paths
572 single_source_shortest_path
573 all_pairs_shortest_path
574 all_pairs_all_shortest_paths
575 """
576 method = "unweighted" if weight is None else method
577 if method == "unweighted":
578 pred = nx.predecessor(G, source)
579 elif method == "dijkstra":
580 pred, dist = nx.dijkstra_predecessor_and_distance(G, source, weight=weight)
581 elif method == "bellman-ford":
582 pred, dist = nx.bellman_ford_predecessor_and_distance(G, source, weight=weight)
583 else:
584 raise ValueError(f"method not supported: {method}")
585 for n in pred:
586 yield n, list(_build_paths_from_predecessors({source}, n, pred))
589@nx._dispatchable(edge_attrs="weight")
590def all_pairs_all_shortest_paths(G, weight=None, method="dijkstra"):
591 """Compute all shortest paths between all nodes.
593 Parameters
594 ----------
595 G : NetworkX graph
597 weight : None, string or function, optional (default = None)
598 If None, every edge has weight/distance/cost 1.
599 If a string, use this edge attribute as the edge weight.
600 Any edge attribute not present defaults to 1.
601 If this is a function, the weight of an edge is the value
602 returned by the function. The function must accept exactly
603 three positional arguments: the two endpoints of an edge and
604 the dictionary of edge attributes for that edge.
605 The function must return a number.
607 method : string, optional (default = 'dijkstra')
608 The algorithm to use to compute the path lengths.
609 Supported options: 'dijkstra', 'bellman-ford'.
610 Other inputs produce a ValueError.
611 If `weight` is None, unweighted graph methods are used, and this
612 suggestion is ignored.
614 Returns
615 -------
616 paths : generator of dictionary
617 Dictionary of arrays, keyed by source and target, of all shortest paths.
619 Raises
620 ------
621 ValueError
622 If `method` is not among the supported options.
624 Examples
625 --------
626 >>> G = nx.cycle_graph(4)
627 >>> dict(nx.all_pairs_all_shortest_paths(G))[0][2]
628 [[0, 1, 2], [0, 3, 2]]
629 >>> dict(nx.all_pairs_all_shortest_paths(G))[0][3]
630 [[0, 3]]
632 Notes
633 -----
634 There may be multiple shortest paths with equal lengths. Unlike
635 all_pairs_shortest_path, this method returns all shortest paths.
637 See Also
638 --------
639 all_pairs_shortest_path
640 single_source_all_shortest_paths
641 """
642 for n in G:
643 yield (
644 n,
645 dict(single_source_all_shortest_paths(G, n, weight=weight, method=method)),
646 )
649def _build_paths_from_predecessors(sources, target, pred):
650 """Compute all simple paths to target, given the predecessors found in
651 pred, terminating when any source in sources is found.
653 Parameters
654 ----------
655 sources : set
656 Starting nodes for path.
658 target : node
659 Ending node for path.
661 pred : dict
662 A dictionary of predecessor lists, keyed by node
664 Returns
665 -------
666 paths : generator of lists
667 A generator of all paths between source and target.
669 Raises
670 ------
671 NetworkXNoPath
672 If `target` cannot be reached from `source`.
674 Notes
675 -----
676 There may be many paths between the sources and target. If there are
677 cycles among the predecessors, this function will not produce all
678 possible paths because doing so would produce infinitely many paths
679 of unbounded length -- instead, we only produce simple paths.
681 See Also
682 --------
683 shortest_path
684 single_source_shortest_path
685 all_pairs_shortest_path
686 all_shortest_paths
687 bellman_ford_path
688 """
689 if target not in pred:
690 raise nx.NetworkXNoPath(f"Target {target} cannot be reached from given sources")
692 seen = {target}
693 stack = [[target, 0]]
694 top = 0
695 while top >= 0:
696 node, i = stack[top]
697 if node in sources:
698 yield [p for p, n in reversed(stack[: top + 1])]
699 if len(pred[node]) > i:
700 stack[top][1] = i + 1
701 next = pred[node][i]
702 if next in seen:
703 continue
704 else:
705 seen.add(next)
706 top += 1
707 if top == len(stack):
708 stack.append([next, 0])
709 else:
710 stack[top][:] = [next, 0]
711 else:
712 seen.discard(node)
713 top -= 1