Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/shortest_paths/weighted.py: 14%
438 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""
2Shortest path algorithms for weighted graphs.
3"""
5from collections import deque
6from heapq import heappop, heappush
7from itertools import count
9import networkx as nx
10from networkx.algorithms.shortest_paths.generic import _build_paths_from_predecessors
12__all__ = [
13 "dijkstra_path",
14 "dijkstra_path_length",
15 "bidirectional_dijkstra",
16 "single_source_dijkstra",
17 "single_source_dijkstra_path",
18 "single_source_dijkstra_path_length",
19 "multi_source_dijkstra",
20 "multi_source_dijkstra_path",
21 "multi_source_dijkstra_path_length",
22 "all_pairs_dijkstra",
23 "all_pairs_dijkstra_path",
24 "all_pairs_dijkstra_path_length",
25 "dijkstra_predecessor_and_distance",
26 "bellman_ford_path",
27 "bellman_ford_path_length",
28 "single_source_bellman_ford",
29 "single_source_bellman_ford_path",
30 "single_source_bellman_ford_path_length",
31 "all_pairs_bellman_ford_path",
32 "all_pairs_bellman_ford_path_length",
33 "bellman_ford_predecessor_and_distance",
34 "negative_edge_cycle",
35 "find_negative_cycle",
36 "goldberg_radzik",
37 "johnson",
38]
41def _weight_function(G, weight):
42 """Returns a function that returns the weight of an edge.
44 The returned function is specifically suitable for input to
45 functions :func:`_dijkstra` and :func:`_bellman_ford_relaxation`.
47 Parameters
48 ----------
49 G : NetworkX graph.
51 weight : string or function
52 If it is callable, `weight` itself is returned. If it is a string,
53 it is assumed to be the name of the edge attribute that represents
54 the weight of an edge. In that case, a function is returned that
55 gets the edge weight according to the specified edge attribute.
57 Returns
58 -------
59 function
60 This function returns a callable that accepts exactly three inputs:
61 a node, an node adjacent to the first one, and the edge attribute
62 dictionary for the eedge joining those nodes. That function returns
63 a number representing the weight of an edge.
65 If `G` is a multigraph, and `weight` is not callable, the
66 minimum edge weight over all parallel edges is returned. If any edge
67 does not have an attribute with key `weight`, it is assumed to
68 have weight one.
70 """
71 if callable(weight):
72 return weight
73 # If the weight keyword argument is not callable, we assume it is a
74 # string representing the edge attribute containing the weight of
75 # the edge.
76 if G.is_multigraph():
77 return lambda u, v, d: min(attr.get(weight, 1) for attr in d.values())
78 return lambda u, v, data: data.get(weight, 1)
81@nx._dispatch(edge_attrs="weight")
82def dijkstra_path(G, source, target, weight="weight"):
83 """Returns the shortest weighted path from source to target in G.
85 Uses Dijkstra's Method to compute the shortest weighted path
86 between two nodes in a graph.
88 Parameters
89 ----------
90 G : NetworkX graph
92 source : node
93 Starting node
95 target : node
96 Ending node
98 weight : string or function
99 If this is a string, then edge weights will be accessed via the
100 edge attribute with this key (that is, the weight of the edge
101 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
102 such edge attribute exists, the weight of the edge is assumed to
103 be one.
105 If this is a function, the weight of an edge is the value
106 returned by the function. The function must accept exactly three
107 positional arguments: the two endpoints of an edge and the
108 dictionary of edge attributes for that edge. The function must
109 return a number or None to indicate a hidden edge.
111 Returns
112 -------
113 path : list
114 List of nodes in a shortest path.
116 Raises
117 ------
118 NodeNotFound
119 If `source` is not in `G`.
121 NetworkXNoPath
122 If no path exists between source and target.
124 Examples
125 --------
126 >>> G = nx.path_graph(5)
127 >>> print(nx.dijkstra_path(G, 0, 4))
128 [0, 1, 2, 3, 4]
130 Find edges of shortest path in Multigraph
132 >>> G = nx.MultiDiGraph()
133 >>> G.add_weighted_edges_from([(1, 2, 0.75), (1, 2, 0.5), (2, 3, 0.5), (1, 3, 1.5)])
134 >>> nodes = nx.dijkstra_path(G, 1, 3)
135 >>> edges = nx.utils.pairwise(nodes)
136 >>> list((u, v, min(G[u][v], key=lambda k: G[u][v][k].get('weight', 1))) for u, v in edges)
137 [(1, 2, 1), (2, 3, 0)]
139 Notes
140 -----
141 Edge weight attributes must be numerical.
142 Distances are calculated as sums of weighted edges traversed.
144 The weight function can be used to hide edges by returning None.
145 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
146 will find the shortest red path.
148 The weight function can be used to include node weights.
150 >>> def func(u, v, d):
151 ... node_u_wt = G.nodes[u].get("node_weight", 1)
152 ... node_v_wt = G.nodes[v].get("node_weight", 1)
153 ... edge_wt = d.get("weight", 1)
154 ... return node_u_wt / 2 + node_v_wt / 2 + edge_wt
156 In this example we take the average of start and end node
157 weights of an edge and add it to the weight of the edge.
159 The function :func:`single_source_dijkstra` computes both
160 path and length-of-path if you need both, use that.
162 See Also
163 --------
164 bidirectional_dijkstra
165 bellman_ford_path
166 single_source_dijkstra
167 """
168 (length, path) = single_source_dijkstra(G, source, target=target, weight=weight)
169 return path
172@nx._dispatch(edge_attrs="weight")
173def dijkstra_path_length(G, source, target, weight="weight"):
174 """Returns the shortest weighted path length in G from source to target.
176 Uses Dijkstra's Method to compute the shortest weighted path length
177 between two nodes in a graph.
179 Parameters
180 ----------
181 G : NetworkX graph
183 source : node label
184 starting node for path
186 target : node label
187 ending node for path
189 weight : string or function
190 If this is a string, then edge weights will be accessed via the
191 edge attribute with this key (that is, the weight of the edge
192 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
193 such edge attribute exists, the weight of the edge is assumed to
194 be one.
196 If this is a function, the weight of an edge is the value
197 returned by the function. The function must accept exactly three
198 positional arguments: the two endpoints of an edge and the
199 dictionary of edge attributes for that edge. The function must
200 return a number or None to indicate a hidden edge.
202 Returns
203 -------
204 length : number
205 Shortest path length.
207 Raises
208 ------
209 NodeNotFound
210 If `source` is not in `G`.
212 NetworkXNoPath
213 If no path exists between source and target.
215 Examples
216 --------
217 >>> G = nx.path_graph(5)
218 >>> nx.dijkstra_path_length(G, 0, 4)
219 4
221 Notes
222 -----
223 Edge weight attributes must be numerical.
224 Distances are calculated as sums of weighted edges traversed.
226 The weight function can be used to hide edges by returning None.
227 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
228 will find the shortest red path.
230 The function :func:`single_source_dijkstra` computes both
231 path and length-of-path if you need both, use that.
233 See Also
234 --------
235 bidirectional_dijkstra
236 bellman_ford_path_length
237 single_source_dijkstra
239 """
240 if source not in G:
241 raise nx.NodeNotFound(f"Node {source} not found in graph")
242 if source == target:
243 return 0
244 weight = _weight_function(G, weight)
245 length = _dijkstra(G, source, weight, target=target)
246 try:
247 return length[target]
248 except KeyError as err:
249 raise nx.NetworkXNoPath(f"Node {target} not reachable from {source}") from err
252@nx._dispatch(edge_attrs="weight")
253def single_source_dijkstra_path(G, source, cutoff=None, weight="weight"):
254 """Find shortest weighted paths in G from a source node.
256 Compute shortest path between source and all other reachable
257 nodes for a weighted graph.
259 Parameters
260 ----------
261 G : NetworkX graph
263 source : node
264 Starting node for path.
266 cutoff : integer or float, optional
267 Length (sum of edge weights) at which the search is stopped.
268 If cutoff is provided, only return paths with summed weight <= cutoff.
270 weight : string or function
271 If this is a string, then edge weights will be accessed via the
272 edge attribute with this key (that is, the weight of the edge
273 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
274 such edge attribute exists, the weight of the edge is assumed to
275 be one.
277 If this is a function, the weight of an edge is the value
278 returned by the function. The function must accept exactly three
279 positional arguments: the two endpoints of an edge and the
280 dictionary of edge attributes for that edge. The function must
281 return a number or None to indicate a hidden edge.
283 Returns
284 -------
285 paths : dictionary
286 Dictionary of shortest path lengths keyed by target.
288 Raises
289 ------
290 NodeNotFound
291 If `source` is not in `G`.
293 Examples
294 --------
295 >>> G = nx.path_graph(5)
296 >>> path = nx.single_source_dijkstra_path(G, 0)
297 >>> path[4]
298 [0, 1, 2, 3, 4]
300 Notes
301 -----
302 Edge weight attributes must be numerical.
303 Distances are calculated as sums of weighted edges traversed.
305 The weight function can be used to hide edges by returning None.
306 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
307 will find the shortest red path.
309 See Also
310 --------
311 single_source_dijkstra, single_source_bellman_ford
313 """
314 return multi_source_dijkstra_path(G, {source}, cutoff=cutoff, weight=weight)
317@nx._dispatch(edge_attrs="weight")
318def single_source_dijkstra_path_length(G, source, cutoff=None, weight="weight"):
319 """Find shortest weighted path lengths in G from a source node.
321 Compute the shortest path length between source and all other
322 reachable nodes for a weighted graph.
324 Parameters
325 ----------
326 G : NetworkX graph
328 source : node label
329 Starting node for path
331 cutoff : integer or float, optional
332 Length (sum of edge weights) at which the search is stopped.
333 If cutoff is provided, only return paths with summed weight <= cutoff.
335 weight : string or function
336 If this is a string, then edge weights will be accessed via the
337 edge attribute with this key (that is, the weight of the edge
338 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
339 such edge attribute exists, the weight of the edge is assumed to
340 be one.
342 If this is a function, the weight of an edge is the value
343 returned by the function. The function must accept exactly three
344 positional arguments: the two endpoints of an edge and the
345 dictionary of edge attributes for that edge. The function must
346 return a number or None to indicate a hidden edge.
348 Returns
349 -------
350 length : dict
351 Dict keyed by node to shortest path length from source.
353 Raises
354 ------
355 NodeNotFound
356 If `source` is not in `G`.
358 Examples
359 --------
360 >>> G = nx.path_graph(5)
361 >>> length = nx.single_source_dijkstra_path_length(G, 0)
362 >>> length[4]
363 4
364 >>> for node in [0, 1, 2, 3, 4]:
365 ... print(f"{node}: {length[node]}")
366 0: 0
367 1: 1
368 2: 2
369 3: 3
370 4: 4
372 Notes
373 -----
374 Edge weight attributes must be numerical.
375 Distances are calculated as sums of weighted edges traversed.
377 The weight function can be used to hide edges by returning None.
378 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
379 will find the shortest red path.
381 See Also
382 --------
383 single_source_dijkstra, single_source_bellman_ford_path_length
385 """
386 return multi_source_dijkstra_path_length(G, {source}, cutoff=cutoff, weight=weight)
389@nx._dispatch(edge_attrs="weight")
390def single_source_dijkstra(G, source, target=None, cutoff=None, weight="weight"):
391 """Find shortest weighted paths and lengths from a source node.
393 Compute the shortest path length between source and all other
394 reachable nodes for a weighted graph.
396 Uses Dijkstra's algorithm to compute shortest paths and lengths
397 between a source and all other reachable nodes in a weighted graph.
399 Parameters
400 ----------
401 G : NetworkX graph
403 source : node label
404 Starting node for path
406 target : node label, optional
407 Ending node for path
409 cutoff : integer or float, optional
410 Length (sum of edge weights) at which the search is stopped.
411 If cutoff is provided, only return paths with summed weight <= cutoff.
414 weight : string or function
415 If this is a string, then edge weights will be accessed via the
416 edge attribute with this key (that is, the weight of the edge
417 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
418 such edge attribute exists, the weight of the edge is assumed to
419 be one.
421 If this is a function, the weight of an edge is the value
422 returned by the function. The function must accept exactly three
423 positional arguments: the two endpoints of an edge and the
424 dictionary of edge attributes for that edge. The function must
425 return a number or None to indicate a hidden edge.
427 Returns
428 -------
429 distance, path : pair of dictionaries, or numeric and list.
430 If target is None, paths and lengths to all nodes are computed.
431 The return value is a tuple of two dictionaries keyed by target nodes.
432 The first dictionary stores distance to each target node.
433 The second stores the path to each target node.
434 If target is not None, returns a tuple (distance, path), where
435 distance is the distance from source to target and path is a list
436 representing the path from source to target.
438 Raises
439 ------
440 NodeNotFound
441 If `source` is not in `G`.
443 Examples
444 --------
445 >>> G = nx.path_graph(5)
446 >>> length, path = nx.single_source_dijkstra(G, 0)
447 >>> length[4]
448 4
449 >>> for node in [0, 1, 2, 3, 4]:
450 ... print(f"{node}: {length[node]}")
451 0: 0
452 1: 1
453 2: 2
454 3: 3
455 4: 4
456 >>> path[4]
457 [0, 1, 2, 3, 4]
458 >>> length, path = nx.single_source_dijkstra(G, 0, 1)
459 >>> length
460 1
461 >>> path
462 [0, 1]
464 Notes
465 -----
466 Edge weight attributes must be numerical.
467 Distances are calculated as sums of weighted edges traversed.
469 The weight function can be used to hide edges by returning None.
470 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
471 will find the shortest red path.
473 Based on the Python cookbook recipe (119466) at
474 https://code.activestate.com/recipes/119466/
476 This algorithm is not guaranteed to work if edge weights
477 are negative or are floating point numbers
478 (overflows and roundoff errors can cause problems).
480 See Also
481 --------
482 single_source_dijkstra_path
483 single_source_dijkstra_path_length
484 single_source_bellman_ford
485 """
486 return multi_source_dijkstra(
487 G, {source}, cutoff=cutoff, target=target, weight=weight
488 )
491@nx._dispatch(edge_attrs="weight")
492def multi_source_dijkstra_path(G, sources, cutoff=None, weight="weight"):
493 """Find shortest weighted paths in G from a given set of source
494 nodes.
496 Compute shortest path between any of the source nodes and all other
497 reachable nodes for a weighted graph.
499 Parameters
500 ----------
501 G : NetworkX graph
503 sources : non-empty set of nodes
504 Starting nodes for paths. If this is just a set containing a
505 single node, then all paths computed by this function will start
506 from that node. If there are two or more nodes in the set, the
507 computed paths may begin from any one of the start nodes.
509 cutoff : integer or float, optional
510 Length (sum of edge weights) at which the search is stopped.
511 If cutoff is provided, only return paths with summed weight <= cutoff.
513 weight : string or function
514 If this is a string, then edge weights will be accessed via the
515 edge attribute with this key (that is, the weight of the edge
516 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
517 such edge attribute exists, the weight of the edge is assumed to
518 be one.
520 If this is a function, the weight of an edge is the value
521 returned by the function. The function must accept exactly three
522 positional arguments: the two endpoints of an edge and the
523 dictionary of edge attributes for that edge. The function must
524 return a number or None to indicate a hidden edge.
526 Returns
527 -------
528 paths : dictionary
529 Dictionary of shortest paths keyed by target.
531 Examples
532 --------
533 >>> G = nx.path_graph(5)
534 >>> path = nx.multi_source_dijkstra_path(G, {0, 4})
535 >>> path[1]
536 [0, 1]
537 >>> path[3]
538 [4, 3]
540 Notes
541 -----
542 Edge weight attributes must be numerical.
543 Distances are calculated as sums of weighted edges traversed.
545 The weight function can be used to hide edges by returning None.
546 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
547 will find the shortest red path.
549 Raises
550 ------
551 ValueError
552 If `sources` is empty.
553 NodeNotFound
554 If any of `sources` is not in `G`.
556 See Also
557 --------
558 multi_source_dijkstra, multi_source_bellman_ford
560 """
561 length, path = multi_source_dijkstra(G, sources, cutoff=cutoff, weight=weight)
562 return path
565@nx._dispatch(edge_attrs="weight")
566def multi_source_dijkstra_path_length(G, sources, cutoff=None, weight="weight"):
567 """Find shortest weighted path lengths in G from a given set of
568 source nodes.
570 Compute the shortest path length between any of the source nodes and
571 all other reachable nodes for a weighted graph.
573 Parameters
574 ----------
575 G : NetworkX graph
577 sources : non-empty set of nodes
578 Starting nodes for paths. If this is just a set containing a
579 single node, then all paths computed by this function will start
580 from that node. If there are two or more nodes in the set, the
581 computed paths may begin from any one of the start nodes.
583 cutoff : integer or float, optional
584 Length (sum of edge weights) at which the search is stopped.
585 If cutoff is provided, only return paths with summed weight <= cutoff.
587 weight : string or function
588 If this is a string, then edge weights will be accessed via the
589 edge attribute with this key (that is, the weight of the edge
590 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
591 such edge attribute exists, the weight of the edge is assumed to
592 be one.
594 If this is a function, the weight of an edge is the value
595 returned by the function. The function must accept exactly three
596 positional arguments: the two endpoints of an edge and the
597 dictionary of edge attributes for that edge. The function must
598 return a number or None to indicate a hidden edge.
600 Returns
601 -------
602 length : dict
603 Dict keyed by node to shortest path length to nearest source.
605 Examples
606 --------
607 >>> G = nx.path_graph(5)
608 >>> length = nx.multi_source_dijkstra_path_length(G, {0, 4})
609 >>> for node in [0, 1, 2, 3, 4]:
610 ... print(f"{node}: {length[node]}")
611 0: 0
612 1: 1
613 2: 2
614 3: 1
615 4: 0
617 Notes
618 -----
619 Edge weight attributes must be numerical.
620 Distances are calculated as sums of weighted edges traversed.
622 The weight function can be used to hide edges by returning None.
623 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
624 will find the shortest red path.
626 Raises
627 ------
628 ValueError
629 If `sources` is empty.
630 NodeNotFound
631 If any of `sources` is not in `G`.
633 See Also
634 --------
635 multi_source_dijkstra
637 """
638 if not sources:
639 raise ValueError("sources must not be empty")
640 for s in sources:
641 if s not in G:
642 raise nx.NodeNotFound(f"Node {s} not found in graph")
643 weight = _weight_function(G, weight)
644 return _dijkstra_multisource(G, sources, weight, cutoff=cutoff)
647@nx._dispatch(edge_attrs="weight")
648def multi_source_dijkstra(G, sources, target=None, cutoff=None, weight="weight"):
649 """Find shortest weighted paths and lengths from a given set of
650 source nodes.
652 Uses Dijkstra's algorithm to compute the shortest paths and lengths
653 between one of the source nodes and the given `target`, or all other
654 reachable nodes if not specified, for a weighted graph.
656 Parameters
657 ----------
658 G : NetworkX graph
660 sources : non-empty set of nodes
661 Starting nodes for paths. If this is just a set containing a
662 single node, then all paths computed by this function will start
663 from that node. If there are two or more nodes in the set, the
664 computed paths may begin from any one of the start nodes.
666 target : node label, optional
667 Ending node for path
669 cutoff : integer or float, optional
670 Length (sum of edge weights) at which the search is stopped.
671 If cutoff is provided, only return paths with summed weight <= cutoff.
673 weight : string or function
674 If this is a string, then edge weights will be accessed via the
675 edge attribute with this key (that is, the weight of the edge
676 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
677 such edge attribute exists, the weight of the edge is assumed to
678 be one.
680 If this is a function, the weight of an edge is the value
681 returned by the function. The function must accept exactly three
682 positional arguments: the two endpoints of an edge and the
683 dictionary of edge attributes for that edge. The function must
684 return a number or None to indicate a hidden edge.
686 Returns
687 -------
688 distance, path : pair of dictionaries, or numeric and list
689 If target is None, returns a tuple of two dictionaries keyed by node.
690 The first dictionary stores distance from one of the source nodes.
691 The second stores the path from one of the sources to that node.
692 If target is not None, returns a tuple of (distance, path) where
693 distance is the distance from source to target and path is a list
694 representing the path from source to target.
696 Examples
697 --------
698 >>> G = nx.path_graph(5)
699 >>> length, path = nx.multi_source_dijkstra(G, {0, 4})
700 >>> for node in [0, 1, 2, 3, 4]:
701 ... print(f"{node}: {length[node]}")
702 0: 0
703 1: 1
704 2: 2
705 3: 1
706 4: 0
707 >>> path[1]
708 [0, 1]
709 >>> path[3]
710 [4, 3]
712 >>> length, path = nx.multi_source_dijkstra(G, {0, 4}, 1)
713 >>> length
714 1
715 >>> path
716 [0, 1]
718 Notes
719 -----
720 Edge weight attributes must be numerical.
721 Distances are calculated as sums of weighted edges traversed.
723 The weight function can be used to hide edges by returning None.
724 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
725 will find the shortest red path.
727 Based on the Python cookbook recipe (119466) at
728 https://code.activestate.com/recipes/119466/
730 This algorithm is not guaranteed to work if edge weights
731 are negative or are floating point numbers
732 (overflows and roundoff errors can cause problems).
734 Raises
735 ------
736 ValueError
737 If `sources` is empty.
738 NodeNotFound
739 If any of `sources` is not in `G`.
741 See Also
742 --------
743 multi_source_dijkstra_path
744 multi_source_dijkstra_path_length
746 """
747 if not sources:
748 raise ValueError("sources must not be empty")
749 for s in sources:
750 if s not in G:
751 raise nx.NodeNotFound(f"Node {s} not found in graph")
752 if target in sources:
753 return (0, [target])
754 weight = _weight_function(G, weight)
755 paths = {source: [source] for source in sources} # dictionary of paths
756 dist = _dijkstra_multisource(
757 G, sources, weight, paths=paths, cutoff=cutoff, target=target
758 )
759 if target is None:
760 return (dist, paths)
761 try:
762 return (dist[target], paths[target])
763 except KeyError as err:
764 raise nx.NetworkXNoPath(f"No path to {target}.") from err
767def _dijkstra(G, source, weight, pred=None, paths=None, cutoff=None, target=None):
768 """Uses Dijkstra's algorithm to find shortest weighted paths from a
769 single source.
771 This is a convenience function for :func:`_dijkstra_multisource`
772 with all the arguments the same, except the keyword argument
773 `sources` set to ``[source]``.
775 """
776 return _dijkstra_multisource(
777 G, [source], weight, pred=pred, paths=paths, cutoff=cutoff, target=target
778 )
781def _dijkstra_multisource(
782 G, sources, weight, pred=None, paths=None, cutoff=None, target=None
783):
784 """Uses Dijkstra's algorithm to find shortest weighted paths
786 Parameters
787 ----------
788 G : NetworkX graph
790 sources : non-empty iterable of nodes
791 Starting nodes for paths. If this is just an iterable containing
792 a single node, then all paths computed by this function will
793 start from that node. If there are two or more nodes in this
794 iterable, the computed paths may begin from any one of the start
795 nodes.
797 weight: function
798 Function with (u, v, data) input that returns that edge's weight
799 or None to indicate a hidden edge
801 pred: dict of lists, optional(default=None)
802 dict to store a list of predecessors keyed by that node
803 If None, predecessors are not stored.
805 paths: dict, optional (default=None)
806 dict to store the path list from source to each node, keyed by node.
807 If None, paths are not stored.
809 target : node label, optional
810 Ending node for path. Search is halted when target is found.
812 cutoff : integer or float, optional
813 Length (sum of edge weights) at which the search is stopped.
814 If cutoff is provided, only return paths with summed weight <= cutoff.
816 Returns
817 -------
818 distance : dictionary
819 A mapping from node to shortest distance to that node from one
820 of the source nodes.
822 Raises
823 ------
824 NodeNotFound
825 If any of `sources` is not in `G`.
827 Notes
828 -----
829 The optional predecessor and path dictionaries can be accessed by
830 the caller through the original pred and paths objects passed
831 as arguments. No need to explicitly return pred or paths.
833 """
834 G_succ = G._adj # For speed-up (and works for both directed and undirected graphs)
836 push = heappush
837 pop = heappop
838 dist = {} # dictionary of final distances
839 seen = {}
840 # fringe is heapq with 3-tuples (distance,c,node)
841 # use the count c to avoid comparing nodes (may not be able to)
842 c = count()
843 fringe = []
844 for source in sources:
845 seen[source] = 0
846 push(fringe, (0, next(c), source))
847 while fringe:
848 (d, _, v) = pop(fringe)
849 if v in dist:
850 continue # already searched this node.
851 dist[v] = d
852 if v == target:
853 break
854 for u, e in G_succ[v].items():
855 cost = weight(v, u, e)
856 if cost is None:
857 continue
858 vu_dist = dist[v] + cost
859 if cutoff is not None:
860 if vu_dist > cutoff:
861 continue
862 if u in dist:
863 u_dist = dist[u]
864 if vu_dist < u_dist:
865 raise ValueError("Contradictory paths found:", "negative weights?")
866 elif pred is not None and vu_dist == u_dist:
867 pred[u].append(v)
868 elif u not in seen or vu_dist < seen[u]:
869 seen[u] = vu_dist
870 push(fringe, (vu_dist, next(c), u))
871 if paths is not None:
872 paths[u] = paths[v] + [u]
873 if pred is not None:
874 pred[u] = [v]
875 elif vu_dist == seen[u]:
876 if pred is not None:
877 pred[u].append(v)
879 # The optional predecessor and path dictionaries can be accessed
880 # by the caller via the pred and paths objects passed as arguments.
881 return dist
884@nx._dispatch(edge_attrs="weight")
885def dijkstra_predecessor_and_distance(G, source, cutoff=None, weight="weight"):
886 """Compute weighted shortest path length and predecessors.
888 Uses Dijkstra's Method to obtain the shortest weighted paths
889 and return dictionaries of predecessors for each node and
890 distance for each node from the `source`.
892 Parameters
893 ----------
894 G : NetworkX graph
896 source : node label
897 Starting node for path
899 cutoff : integer or float, optional
900 Length (sum of edge weights) at which the search is stopped.
901 If cutoff is provided, only return paths with summed weight <= cutoff.
903 weight : string or function
904 If this is a string, then edge weights will be accessed via the
905 edge attribute with this key (that is, the weight of the edge
906 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
907 such edge attribute exists, the weight of the edge is assumed to
908 be one.
910 If this is a function, the weight of an edge is the value
911 returned by the function. The function must accept exactly three
912 positional arguments: the two endpoints of an edge and the
913 dictionary of edge attributes for that edge. The function must
914 return a number or None to indicate a hidden edge.
916 Returns
917 -------
918 pred, distance : dictionaries
919 Returns two dictionaries representing a list of predecessors
920 of a node and the distance to each node.
922 Raises
923 ------
924 NodeNotFound
925 If `source` is not in `G`.
927 Notes
928 -----
929 Edge weight attributes must be numerical.
930 Distances are calculated as sums of weighted edges traversed.
932 The list of predecessors contains more than one element only when
933 there are more than one shortest paths to the key node.
935 Examples
936 --------
937 >>> G = nx.path_graph(5, create_using=nx.DiGraph())
938 >>> pred, dist = nx.dijkstra_predecessor_and_distance(G, 0)
939 >>> sorted(pred.items())
940 [(0, []), (1, [0]), (2, [1]), (3, [2]), (4, [3])]
941 >>> sorted(dist.items())
942 [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
944 >>> pred, dist = nx.dijkstra_predecessor_and_distance(G, 0, 1)
945 >>> sorted(pred.items())
946 [(0, []), (1, [0])]
947 >>> sorted(dist.items())
948 [(0, 0), (1, 1)]
949 """
950 if source not in G:
951 raise nx.NodeNotFound(f"Node {source} is not found in the graph")
952 weight = _weight_function(G, weight)
953 pred = {source: []} # dictionary of predecessors
954 return (pred, _dijkstra(G, source, weight, pred=pred, cutoff=cutoff))
957@nx._dispatch(edge_attrs="weight")
958def all_pairs_dijkstra(G, cutoff=None, weight="weight"):
959 """Find shortest weighted paths and lengths between all nodes.
961 Parameters
962 ----------
963 G : NetworkX graph
965 cutoff : integer or float, optional
966 Length (sum of edge weights) at which the search is stopped.
967 If cutoff is provided, only return paths with summed weight <= cutoff.
969 weight : string or function
970 If this is a string, then edge weights will be accessed via the
971 edge attribute with this key (that is, the weight of the edge
972 joining `u` to `v` will be ``G.edge[u][v][weight]``). If no
973 such edge attribute exists, the weight of the edge is assumed to
974 be one.
976 If this is a function, the weight of an edge is the value
977 returned by the function. The function must accept exactly three
978 positional arguments: the two endpoints of an edge and the
979 dictionary of edge attributes for that edge. The function must
980 return a number or None to indicate a hidden edge.
982 Yields
983 ------
984 (node, (distance, path)) : (node obj, (dict, dict))
985 Each source node has two associated dicts. The first holds distance
986 keyed by target and the second holds paths keyed by target.
987 (See single_source_dijkstra for the source/target node terminology.)
988 If desired you can apply `dict()` to this function to create a dict
989 keyed by source node to the two dicts.
991 Examples
992 --------
993 >>> G = nx.path_graph(5)
994 >>> len_path = dict(nx.all_pairs_dijkstra(G))
995 >>> len_path[3][0][1]
996 2
997 >>> for node in [0, 1, 2, 3, 4]:
998 ... print(f"3 - {node}: {len_path[3][0][node]}")
999 3 - 0: 3
1000 3 - 1: 2
1001 3 - 2: 1
1002 3 - 3: 0
1003 3 - 4: 1
1004 >>> len_path[3][1][1]
1005 [3, 2, 1]
1006 >>> for n, (dist, path) in nx.all_pairs_dijkstra(G):
1007 ... print(path[1])
1008 [0, 1]
1009 [1]
1010 [2, 1]
1011 [3, 2, 1]
1012 [4, 3, 2, 1]
1014 Notes
1015 -----
1016 Edge weight attributes must be numerical.
1017 Distances are calculated as sums of weighted edges traversed.
1019 The yielded dicts only have keys for reachable nodes.
1020 """
1021 for n in G:
1022 dist, path = single_source_dijkstra(G, n, cutoff=cutoff, weight=weight)
1023 yield (n, (dist, path))
1026@nx._dispatch(edge_attrs="weight")
1027def all_pairs_dijkstra_path_length(G, cutoff=None, weight="weight"):
1028 """Compute shortest path lengths between all nodes in a weighted graph.
1030 Parameters
1031 ----------
1032 G : NetworkX graph
1034 cutoff : integer or float, optional
1035 Length (sum of edge weights) at which the search is stopped.
1036 If cutoff is provided, only return paths with summed weight <= cutoff.
1038 weight : string or function
1039 If this is a string, then edge weights will be accessed via the
1040 edge attribute with this key (that is, the weight of the edge
1041 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1042 such edge attribute exists, the weight of the edge is assumed to
1043 be one.
1045 If this is a function, the weight of an edge is the value
1046 returned by the function. The function must accept exactly three
1047 positional arguments: the two endpoints of an edge and the
1048 dictionary of edge attributes for that edge. The function must
1049 return a number or None to indicate a hidden edge.
1051 Returns
1052 -------
1053 distance : iterator
1054 (source, dictionary) iterator with dictionary keyed by target and
1055 shortest path length as the key value.
1057 Examples
1058 --------
1059 >>> G = nx.path_graph(5)
1060 >>> length = dict(nx.all_pairs_dijkstra_path_length(G))
1061 >>> for node in [0, 1, 2, 3, 4]:
1062 ... print(f"1 - {node}: {length[1][node]}")
1063 1 - 0: 1
1064 1 - 1: 0
1065 1 - 2: 1
1066 1 - 3: 2
1067 1 - 4: 3
1068 >>> length[3][2]
1069 1
1070 >>> length[2][2]
1071 0
1073 Notes
1074 -----
1075 Edge weight attributes must be numerical.
1076 Distances are calculated as sums of weighted edges traversed.
1078 The dictionary returned only has keys for reachable node pairs.
1079 """
1080 length = single_source_dijkstra_path_length
1081 for n in G:
1082 yield (n, length(G, n, cutoff=cutoff, weight=weight))
1085@nx._dispatch(edge_attrs="weight")
1086def all_pairs_dijkstra_path(G, cutoff=None, weight="weight"):
1087 """Compute shortest paths between all nodes in a weighted graph.
1089 Parameters
1090 ----------
1091 G : NetworkX graph
1093 cutoff : integer or float, optional
1094 Length (sum of edge weights) at which the search is stopped.
1095 If cutoff is provided, only return paths with summed weight <= cutoff.
1097 weight : string or function
1098 If this is a string, then edge weights will be accessed via the
1099 edge attribute with this key (that is, the weight of the edge
1100 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1101 such edge attribute exists, the weight of the edge is assumed to
1102 be one.
1104 If this is a function, the weight of an edge is the value
1105 returned by the function. The function must accept exactly three
1106 positional arguments: the two endpoints of an edge and the
1107 dictionary of edge attributes for that edge. The function must
1108 return a number or None to indicate a hidden edge.
1110 Returns
1111 -------
1112 paths : iterator
1113 (source, dictionary) iterator with dictionary keyed by target and
1114 shortest path as the key value.
1116 Examples
1117 --------
1118 >>> G = nx.path_graph(5)
1119 >>> path = dict(nx.all_pairs_dijkstra_path(G))
1120 >>> path[0][4]
1121 [0, 1, 2, 3, 4]
1123 Notes
1124 -----
1125 Edge weight attributes must be numerical.
1126 Distances are calculated as sums of weighted edges traversed.
1128 See Also
1129 --------
1130 floyd_warshall, all_pairs_bellman_ford_path
1132 """
1133 path = single_source_dijkstra_path
1134 # TODO This can be trivially parallelized.
1135 for n in G:
1136 yield (n, path(G, n, cutoff=cutoff, weight=weight))
1139@nx._dispatch(edge_attrs="weight")
1140def bellman_ford_predecessor_and_distance(
1141 G, source, target=None, weight="weight", heuristic=False
1142):
1143 """Compute shortest path lengths and predecessors on shortest paths
1144 in weighted graphs.
1146 The algorithm has a running time of $O(mn)$ where $n$ is the number of
1147 nodes and $m$ is the number of edges. It is slower than Dijkstra but
1148 can handle negative edge weights.
1150 If a negative cycle is detected, you can use :func:`find_negative_cycle`
1151 to return the cycle and examine it. Shortest paths are not defined when
1152 a negative cycle exists because once reached, the path can cycle forever
1153 to build up arbitrarily low weights.
1155 Parameters
1156 ----------
1157 G : NetworkX graph
1158 The algorithm works for all types of graphs, including directed
1159 graphs and multigraphs.
1161 source: node label
1162 Starting node for path
1164 target : node label, optional
1165 Ending node for path
1167 weight : string or function
1168 If this is a string, then edge weights will be accessed via the
1169 edge attribute with this key (that is, the weight of the edge
1170 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1171 such edge attribute exists, the weight of the edge is assumed to
1172 be one.
1174 If this is a function, the weight of an edge is the value
1175 returned by the function. The function must accept exactly three
1176 positional arguments: the two endpoints of an edge and the
1177 dictionary of edge attributes for that edge. The function must
1178 return a number.
1180 heuristic : bool
1181 Determines whether to use a heuristic to early detect negative
1182 cycles at a hopefully negligible cost.
1184 Returns
1185 -------
1186 pred, dist : dictionaries
1187 Returns two dictionaries keyed by node to predecessor in the
1188 path and to the distance from the source respectively.
1190 Raises
1191 ------
1192 NodeNotFound
1193 If `source` is not in `G`.
1195 NetworkXUnbounded
1196 If the (di)graph contains a negative (di)cycle, the
1197 algorithm raises an exception to indicate the presence of the
1198 negative (di)cycle. Note: any negative weight edge in an
1199 undirected graph is a negative cycle.
1201 Examples
1202 --------
1203 >>> G = nx.path_graph(5, create_using=nx.DiGraph())
1204 >>> pred, dist = nx.bellman_ford_predecessor_and_distance(G, 0)
1205 >>> sorted(pred.items())
1206 [(0, []), (1, [0]), (2, [1]), (3, [2]), (4, [3])]
1207 >>> sorted(dist.items())
1208 [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
1210 >>> pred, dist = nx.bellman_ford_predecessor_and_distance(G, 0, 1)
1211 >>> sorted(pred.items())
1212 [(0, []), (1, [0]), (2, [1]), (3, [2]), (4, [3])]
1213 >>> sorted(dist.items())
1214 [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
1216 >>> G = nx.cycle_graph(5, create_using=nx.DiGraph())
1217 >>> G[1][2]["weight"] = -7
1218 >>> nx.bellman_ford_predecessor_and_distance(G, 0)
1219 Traceback (most recent call last):
1220 ...
1221 networkx.exception.NetworkXUnbounded: Negative cycle detected.
1223 See Also
1224 --------
1225 find_negative_cycle
1227 Notes
1228 -----
1229 Edge weight attributes must be numerical.
1230 Distances are calculated as sums of weighted edges traversed.
1232 The dictionaries returned only have keys for nodes reachable from
1233 the source.
1235 In the case where the (di)graph is not connected, if a component
1236 not containing the source contains a negative (di)cycle, it
1237 will not be detected.
1239 In NetworkX v2.1 and prior, the source node had predecessor `[None]`.
1240 In NetworkX v2.2 this changed to the source node having predecessor `[]`
1241 """
1242 if source not in G:
1243 raise nx.NodeNotFound(f"Node {source} is not found in the graph")
1244 weight = _weight_function(G, weight)
1245 if G.is_multigraph():
1246 if any(
1247 weight(u, v, {k: d}) < 0
1248 for u, v, k, d in nx.selfloop_edges(G, keys=True, data=True)
1249 ):
1250 raise nx.NetworkXUnbounded("Negative cycle detected.")
1251 else:
1252 if any(weight(u, v, d) < 0 for u, v, d in nx.selfloop_edges(G, data=True)):
1253 raise nx.NetworkXUnbounded("Negative cycle detected.")
1255 dist = {source: 0}
1256 pred = {source: []}
1258 if len(G) == 1:
1259 return pred, dist
1261 weight = _weight_function(G, weight)
1263 dist = _bellman_ford(
1264 G, [source], weight, pred=pred, dist=dist, target=target, heuristic=heuristic
1265 )
1266 return (pred, dist)
1269def _bellman_ford(
1270 G,
1271 source,
1272 weight,
1273 pred=None,
1274 paths=None,
1275 dist=None,
1276 target=None,
1277 heuristic=True,
1278):
1279 """Calls relaxation loop for Bellman–Ford algorithm and builds paths
1281 This is an implementation of the SPFA variant.
1282 See https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm
1284 Parameters
1285 ----------
1286 G : NetworkX graph
1288 source: list
1289 List of source nodes. The shortest path from any of the source
1290 nodes will be found if multiple sources are provided.
1292 weight : function
1293 The weight of an edge is the value returned by the function. The
1294 function must accept exactly three positional arguments: the two
1295 endpoints of an edge and the dictionary of edge attributes for
1296 that edge. The function must return a number.
1298 pred: dict of lists, optional (default=None)
1299 dict to store a list of predecessors keyed by that node
1300 If None, predecessors are not stored
1302 paths: dict, optional (default=None)
1303 dict to store the path list from source to each node, keyed by node
1304 If None, paths are not stored
1306 dist: dict, optional (default=None)
1307 dict to store distance from source to the keyed node
1308 If None, returned dist dict contents default to 0 for every node in the
1309 source list
1311 target: node label, optional
1312 Ending node for path. Path lengths to other destinations may (and
1313 probably will) be incorrect.
1315 heuristic : bool
1316 Determines whether to use a heuristic to early detect negative
1317 cycles at a hopefully negligible cost.
1319 Returns
1320 -------
1321 dist : dict
1322 Returns a dict keyed by node to the distance from the source.
1323 Dicts for paths and pred are in the mutated input dicts by those names.
1325 Raises
1326 ------
1327 NodeNotFound
1328 If any of `source` is not in `G`.
1330 NetworkXUnbounded
1331 If the (di)graph contains a negative (di)cycle, the
1332 algorithm raises an exception to indicate the presence of the
1333 negative (di)cycle. Note: any negative weight edge in an
1334 undirected graph is a negative cycle
1335 """
1336 if pred is None:
1337 pred = {v: [] for v in source}
1339 if dist is None:
1340 dist = {v: 0 for v in source}
1342 negative_cycle_found = _inner_bellman_ford(
1343 G,
1344 source,
1345 weight,
1346 pred,
1347 dist,
1348 heuristic,
1349 )
1350 if negative_cycle_found is not None:
1351 raise nx.NetworkXUnbounded("Negative cycle detected.")
1353 if paths is not None:
1354 sources = set(source)
1355 dsts = [target] if target is not None else pred
1356 for dst in dsts:
1357 gen = _build_paths_from_predecessors(sources, dst, pred)
1358 paths[dst] = next(gen)
1360 return dist
1363def _inner_bellman_ford(
1364 G,
1365 sources,
1366 weight,
1367 pred,
1368 dist=None,
1369 heuristic=True,
1370):
1371 """Inner Relaxation loop for Bellman–Ford algorithm.
1373 This is an implementation of the SPFA variant.
1374 See https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm
1376 Parameters
1377 ----------
1378 G : NetworkX graph
1380 source: list
1381 List of source nodes. The shortest path from any of the source
1382 nodes will be found if multiple sources are provided.
1384 weight : function
1385 The weight of an edge is the value returned by the function. The
1386 function must accept exactly three positional arguments: the two
1387 endpoints of an edge and the dictionary of edge attributes for
1388 that edge. The function must return a number.
1390 pred: dict of lists
1391 dict to store a list of predecessors keyed by that node
1393 dist: dict, optional (default=None)
1394 dict to store distance from source to the keyed node
1395 If None, returned dist dict contents default to 0 for every node in the
1396 source list
1398 heuristic : bool
1399 Determines whether to use a heuristic to early detect negative
1400 cycles at a hopefully negligible cost.
1402 Returns
1403 -------
1404 node or None
1405 Return a node `v` where processing discovered a negative cycle.
1406 If no negative cycle found, return None.
1408 Raises
1409 ------
1410 NodeNotFound
1411 If any of `source` is not in `G`.
1412 """
1413 for s in sources:
1414 if s not in G:
1415 raise nx.NodeNotFound(f"Source {s} not in G")
1417 if pred is None:
1418 pred = {v: [] for v in sources}
1420 if dist is None:
1421 dist = {v: 0 for v in sources}
1423 # Heuristic Storage setup. Note: use None because nodes cannot be None
1424 nonexistent_edge = (None, None)
1425 pred_edge = {v: None for v in sources}
1426 recent_update = {v: nonexistent_edge for v in sources}
1428 G_succ = G._adj # For speed-up (and works for both directed and undirected graphs)
1429 inf = float("inf")
1430 n = len(G)
1432 count = {}
1433 q = deque(sources)
1434 in_q = set(sources)
1435 while q:
1436 u = q.popleft()
1437 in_q.remove(u)
1439 # Skip relaxations if any of the predecessors of u is in the queue.
1440 if all(pred_u not in in_q for pred_u in pred[u]):
1441 dist_u = dist[u]
1442 for v, e in G_succ[u].items():
1443 dist_v = dist_u + weight(u, v, e)
1445 if dist_v < dist.get(v, inf):
1446 # In this conditional branch we are updating the path with v.
1447 # If it happens that some earlier update also added node v
1448 # that implies the existence of a negative cycle since
1449 # after the update node v would lie on the update path twice.
1450 # The update path is stored up to one of the source nodes,
1451 # therefore u is always in the dict recent_update
1452 if heuristic:
1453 if v in recent_update[u]:
1454 # Negative cycle found!
1455 pred[v].append(u)
1456 return v
1458 # Transfer the recent update info from u to v if the
1459 # same source node is the head of the update path.
1460 # If the source node is responsible for the cost update,
1461 # then clear the history and use it instead.
1462 if v in pred_edge and pred_edge[v] == u:
1463 recent_update[v] = recent_update[u]
1464 else:
1465 recent_update[v] = (u, v)
1467 if v not in in_q:
1468 q.append(v)
1469 in_q.add(v)
1470 count_v = count.get(v, 0) + 1
1471 if count_v == n:
1472 # Negative cycle found!
1473 return v
1475 count[v] = count_v
1476 dist[v] = dist_v
1477 pred[v] = [u]
1478 pred_edge[v] = u
1480 elif dist.get(v) is not None and dist_v == dist.get(v):
1481 pred[v].append(u)
1483 # successfully found shortest_path. No negative cycles found.
1484 return None
1487@nx._dispatch(edge_attrs="weight")
1488def bellman_ford_path(G, source, target, weight="weight"):
1489 """Returns the shortest path from source to target in a weighted graph G.
1491 Parameters
1492 ----------
1493 G : NetworkX graph
1495 source : node
1496 Starting node
1498 target : node
1499 Ending node
1501 weight : string or function (default="weight")
1502 If this is a string, then edge weights will be accessed via the
1503 edge attribute with this key (that is, the weight of the edge
1504 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1505 such edge attribute exists, the weight of the edge is assumed to
1506 be one.
1508 If this is a function, the weight of an edge is the value
1509 returned by the function. The function must accept exactly three
1510 positional arguments: the two endpoints of an edge and the
1511 dictionary of edge attributes for that edge. The function must
1512 return a number.
1514 Returns
1515 -------
1516 path : list
1517 List of nodes in a shortest path.
1519 Raises
1520 ------
1521 NodeNotFound
1522 If `source` is not in `G`.
1524 NetworkXNoPath
1525 If no path exists between source and target.
1527 Examples
1528 --------
1529 >>> G = nx.path_graph(5)
1530 >>> nx.bellman_ford_path(G, 0, 4)
1531 [0, 1, 2, 3, 4]
1533 Notes
1534 -----
1535 Edge weight attributes must be numerical.
1536 Distances are calculated as sums of weighted edges traversed.
1538 See Also
1539 --------
1540 dijkstra_path, bellman_ford_path_length
1541 """
1542 length, path = single_source_bellman_ford(G, source, target=target, weight=weight)
1543 return path
1546@nx._dispatch(edge_attrs="weight")
1547def bellman_ford_path_length(G, source, target, weight="weight"):
1548 """Returns the shortest path length from source to target
1549 in a weighted graph.
1551 Parameters
1552 ----------
1553 G : NetworkX graph
1555 source : node label
1556 starting node for path
1558 target : node label
1559 ending node for path
1561 weight : string or function (default="weight")
1562 If this is a string, then edge weights will be accessed via the
1563 edge attribute with this key (that is, the weight of the edge
1564 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1565 such edge attribute exists, the weight of the edge is assumed to
1566 be one.
1568 If this is a function, the weight of an edge is the value
1569 returned by the function. The function must accept exactly three
1570 positional arguments: the two endpoints of an edge and the
1571 dictionary of edge attributes for that edge. The function must
1572 return a number.
1574 Returns
1575 -------
1576 length : number
1577 Shortest path length.
1579 Raises
1580 ------
1581 NodeNotFound
1582 If `source` is not in `G`.
1584 NetworkXNoPath
1585 If no path exists between source and target.
1587 Examples
1588 --------
1589 >>> G = nx.path_graph(5)
1590 >>> nx.bellman_ford_path_length(G, 0, 4)
1591 4
1593 Notes
1594 -----
1595 Edge weight attributes must be numerical.
1596 Distances are calculated as sums of weighted edges traversed.
1598 See Also
1599 --------
1600 dijkstra_path_length, bellman_ford_path
1601 """
1602 if source == target:
1603 if source not in G:
1604 raise nx.NodeNotFound(f"Node {source} not found in graph")
1605 return 0
1607 weight = _weight_function(G, weight)
1609 length = _bellman_ford(G, [source], weight, target=target)
1611 try:
1612 return length[target]
1613 except KeyError as err:
1614 raise nx.NetworkXNoPath(f"node {target} not reachable from {source}") from err
1617@nx._dispatch(edge_attrs="weight")
1618def single_source_bellman_ford_path(G, source, weight="weight"):
1619 """Compute shortest path between source and all other reachable
1620 nodes for a weighted graph.
1622 Parameters
1623 ----------
1624 G : NetworkX graph
1626 source : node
1627 Starting node for path.
1629 weight : string or function (default="weight")
1630 If this is a string, then edge weights will be accessed via the
1631 edge attribute with this key (that is, the weight of the edge
1632 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1633 such edge attribute exists, the weight of the edge is assumed to
1634 be one.
1636 If this is a function, the weight of an edge is the value
1637 returned by the function. The function must accept exactly three
1638 positional arguments: the two endpoints of an edge and the
1639 dictionary of edge attributes for that edge. The function must
1640 return a number.
1642 Returns
1643 -------
1644 paths : dictionary
1645 Dictionary of shortest path lengths keyed by target.
1647 Raises
1648 ------
1649 NodeNotFound
1650 If `source` is not in `G`.
1652 Examples
1653 --------
1654 >>> G = nx.path_graph(5)
1655 >>> path = nx.single_source_bellman_ford_path(G, 0)
1656 >>> path[4]
1657 [0, 1, 2, 3, 4]
1659 Notes
1660 -----
1661 Edge weight attributes must be numerical.
1662 Distances are calculated as sums of weighted edges traversed.
1664 See Also
1665 --------
1666 single_source_dijkstra, single_source_bellman_ford
1668 """
1669 (length, path) = single_source_bellman_ford(G, source, weight=weight)
1670 return path
1673@nx._dispatch(edge_attrs="weight")
1674def single_source_bellman_ford_path_length(G, source, weight="weight"):
1675 """Compute the shortest path length between source and all other
1676 reachable nodes for a weighted graph.
1678 Parameters
1679 ----------
1680 G : NetworkX graph
1682 source : node label
1683 Starting node for path
1685 weight : string or function (default="weight")
1686 If this is a string, then edge weights will be accessed via the
1687 edge attribute with this key (that is, the weight of the edge
1688 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1689 such edge attribute exists, the weight of the edge is assumed to
1690 be one.
1692 If this is a function, the weight of an edge is the value
1693 returned by the function. The function must accept exactly three
1694 positional arguments: the two endpoints of an edge and the
1695 dictionary of edge attributes for that edge. The function must
1696 return a number.
1698 Returns
1699 -------
1700 length : dictionary
1701 Dictionary of shortest path length keyed by target
1703 Raises
1704 ------
1705 NodeNotFound
1706 If `source` is not in `G`.
1708 Examples
1709 --------
1710 >>> G = nx.path_graph(5)
1711 >>> length = nx.single_source_bellman_ford_path_length(G, 0)
1712 >>> length[4]
1713 4
1714 >>> for node in [0, 1, 2, 3, 4]:
1715 ... print(f"{node}: {length[node]}")
1716 0: 0
1717 1: 1
1718 2: 2
1719 3: 3
1720 4: 4
1722 Notes
1723 -----
1724 Edge weight attributes must be numerical.
1725 Distances are calculated as sums of weighted edges traversed.
1727 See Also
1728 --------
1729 single_source_dijkstra, single_source_bellman_ford
1731 """
1732 weight = _weight_function(G, weight)
1733 return _bellman_ford(G, [source], weight)
1736@nx._dispatch(edge_attrs="weight")
1737def single_source_bellman_ford(G, source, target=None, weight="weight"):
1738 """Compute shortest paths and lengths in a weighted graph G.
1740 Uses Bellman-Ford algorithm for shortest paths.
1742 Parameters
1743 ----------
1744 G : NetworkX graph
1746 source : node label
1747 Starting node for path
1749 target : node label, optional
1750 Ending node for path
1752 weight : string or function
1753 If this is a string, then edge weights will be accessed via the
1754 edge attribute with this key (that is, the weight of the edge
1755 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1756 such edge attribute exists, the weight of the edge is assumed to
1757 be one.
1759 If this is a function, the weight of an edge is the value
1760 returned by the function. The function must accept exactly three
1761 positional arguments: the two endpoints of an edge and the
1762 dictionary of edge attributes for that edge. The function must
1763 return a number.
1765 Returns
1766 -------
1767 distance, path : pair of dictionaries, or numeric and list
1768 If target is None, returns a tuple of two dictionaries keyed by node.
1769 The first dictionary stores distance from one of the source nodes.
1770 The second stores the path from one of the sources to that node.
1771 If target is not None, returns a tuple of (distance, path) where
1772 distance is the distance from source to target and path is a list
1773 representing the path from source to target.
1775 Raises
1776 ------
1777 NodeNotFound
1778 If `source` is not in `G`.
1780 Examples
1781 --------
1782 >>> G = nx.path_graph(5)
1783 >>> length, path = nx.single_source_bellman_ford(G, 0)
1784 >>> length[4]
1785 4
1786 >>> for node in [0, 1, 2, 3, 4]:
1787 ... print(f"{node}: {length[node]}")
1788 0: 0
1789 1: 1
1790 2: 2
1791 3: 3
1792 4: 4
1793 >>> path[4]
1794 [0, 1, 2, 3, 4]
1795 >>> length, path = nx.single_source_bellman_ford(G, 0, 1)
1796 >>> length
1797 1
1798 >>> path
1799 [0, 1]
1801 Notes
1802 -----
1803 Edge weight attributes must be numerical.
1804 Distances are calculated as sums of weighted edges traversed.
1806 See Also
1807 --------
1808 single_source_dijkstra
1809 single_source_bellman_ford_path
1810 single_source_bellman_ford_path_length
1811 """
1812 if source == target:
1813 if source not in G:
1814 raise nx.NodeNotFound(f"Node {source} is not found in the graph")
1815 return (0, [source])
1817 weight = _weight_function(G, weight)
1819 paths = {source: [source]} # dictionary of paths
1820 dist = _bellman_ford(G, [source], weight, paths=paths, target=target)
1821 if target is None:
1822 return (dist, paths)
1823 try:
1824 return (dist[target], paths[target])
1825 except KeyError as err:
1826 msg = f"Node {target} not reachable from {source}"
1827 raise nx.NetworkXNoPath(msg) from err
1830@nx._dispatch(edge_attrs="weight")
1831def all_pairs_bellman_ford_path_length(G, weight="weight"):
1832 """Compute shortest path lengths between all nodes in a weighted graph.
1834 Parameters
1835 ----------
1836 G : NetworkX graph
1838 weight : string or function (default="weight")
1839 If this is a string, then edge weights will be accessed via the
1840 edge attribute with this key (that is, the weight of the edge
1841 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1842 such edge attribute exists, the weight of the edge is assumed to
1843 be one.
1845 If this is a function, the weight of an edge is the value
1846 returned by the function. The function must accept exactly three
1847 positional arguments: the two endpoints of an edge and the
1848 dictionary of edge attributes for that edge. The function must
1849 return a number.
1851 Returns
1852 -------
1853 distance : iterator
1854 (source, dictionary) iterator with dictionary keyed by target and
1855 shortest path length as the key value.
1857 Examples
1858 --------
1859 >>> G = nx.path_graph(5)
1860 >>> length = dict(nx.all_pairs_bellman_ford_path_length(G))
1861 >>> for node in [0, 1, 2, 3, 4]:
1862 ... print(f"1 - {node}: {length[1][node]}")
1863 1 - 0: 1
1864 1 - 1: 0
1865 1 - 2: 1
1866 1 - 3: 2
1867 1 - 4: 3
1868 >>> length[3][2]
1869 1
1870 >>> length[2][2]
1871 0
1873 Notes
1874 -----
1875 Edge weight attributes must be numerical.
1876 Distances are calculated as sums of weighted edges traversed.
1878 The dictionary returned only has keys for reachable node pairs.
1879 """
1880 length = single_source_bellman_ford_path_length
1881 for n in G:
1882 yield (n, dict(length(G, n, weight=weight)))
1885@nx._dispatch(edge_attrs="weight")
1886def all_pairs_bellman_ford_path(G, weight="weight"):
1887 """Compute shortest paths between all nodes in a weighted graph.
1889 Parameters
1890 ----------
1891 G : NetworkX graph
1893 weight : string or function (default="weight")
1894 If this is a string, then edge weights will be accessed via the
1895 edge attribute with this key (that is, the weight of the edge
1896 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1897 such edge attribute exists, the weight of the edge is assumed to
1898 be one.
1900 If this is a function, the weight of an edge is the value
1901 returned by the function. The function must accept exactly three
1902 positional arguments: the two endpoints of an edge and the
1903 dictionary of edge attributes for that edge. The function must
1904 return a number.
1906 Returns
1907 -------
1908 paths : iterator
1909 (source, dictionary) iterator with dictionary keyed by target and
1910 shortest path as the key value.
1912 Examples
1913 --------
1914 >>> G = nx.path_graph(5)
1915 >>> path = dict(nx.all_pairs_bellman_ford_path(G))
1916 >>> path[0][4]
1917 [0, 1, 2, 3, 4]
1919 Notes
1920 -----
1921 Edge weight attributes must be numerical.
1922 Distances are calculated as sums of weighted edges traversed.
1924 See Also
1925 --------
1926 floyd_warshall, all_pairs_dijkstra_path
1928 """
1929 path = single_source_bellman_ford_path
1930 # TODO This can be trivially parallelized.
1931 for n in G:
1932 yield (n, path(G, n, weight=weight))
1935@nx._dispatch(edge_attrs="weight")
1936def goldberg_radzik(G, source, weight="weight"):
1937 """Compute shortest path lengths and predecessors on shortest paths
1938 in weighted graphs.
1940 The algorithm has a running time of $O(mn)$ where $n$ is the number of
1941 nodes and $m$ is the number of edges. It is slower than Dijkstra but
1942 can handle negative edge weights.
1944 Parameters
1945 ----------
1946 G : NetworkX graph
1947 The algorithm works for all types of graphs, including directed
1948 graphs and multigraphs.
1950 source: node label
1951 Starting node for path
1953 weight : string or function
1954 If this is a string, then edge weights will be accessed via the
1955 edge attribute with this key (that is, the weight of the edge
1956 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1957 such edge attribute exists, the weight of the edge is assumed to
1958 be one.
1960 If this is a function, the weight of an edge is the value
1961 returned by the function. The function must accept exactly three
1962 positional arguments: the two endpoints of an edge and the
1963 dictionary of edge attributes for that edge. The function must
1964 return a number.
1966 Returns
1967 -------
1968 pred, dist : dictionaries
1969 Returns two dictionaries keyed by node to predecessor in the
1970 path and to the distance from the source respectively.
1972 Raises
1973 ------
1974 NodeNotFound
1975 If `source` is not in `G`.
1977 NetworkXUnbounded
1978 If the (di)graph contains a negative (di)cycle, the
1979 algorithm raises an exception to indicate the presence of the
1980 negative (di)cycle. Note: any negative weight edge in an
1981 undirected graph is a negative cycle.
1983 As of NetworkX v3.2, a zero weight cycle is no longer
1984 incorrectly reported as a negative weight cycle.
1987 Examples
1988 --------
1989 >>> G = nx.path_graph(5, create_using=nx.DiGraph())
1990 >>> pred, dist = nx.goldberg_radzik(G, 0)
1991 >>> sorted(pred.items())
1992 [(0, None), (1, 0), (2, 1), (3, 2), (4, 3)]
1993 >>> sorted(dist.items())
1994 [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
1996 >>> G = nx.cycle_graph(5, create_using=nx.DiGraph())
1997 >>> G[1][2]["weight"] = -7
1998 >>> nx.goldberg_radzik(G, 0)
1999 Traceback (most recent call last):
2000 ...
2001 networkx.exception.NetworkXUnbounded: Negative cycle detected.
2003 Notes
2004 -----
2005 Edge weight attributes must be numerical.
2006 Distances are calculated as sums of weighted edges traversed.
2008 The dictionaries returned only have keys for nodes reachable from
2009 the source.
2011 In the case where the (di)graph is not connected, if a component
2012 not containing the source contains a negative (di)cycle, it
2013 will not be detected.
2015 """
2016 if source not in G:
2017 raise nx.NodeNotFound(f"Node {source} is not found in the graph")
2018 weight = _weight_function(G, weight)
2019 if G.is_multigraph():
2020 if any(
2021 weight(u, v, {k: d}) < 0
2022 for u, v, k, d in nx.selfloop_edges(G, keys=True, data=True)
2023 ):
2024 raise nx.NetworkXUnbounded("Negative cycle detected.")
2025 else:
2026 if any(weight(u, v, d) < 0 for u, v, d in nx.selfloop_edges(G, data=True)):
2027 raise nx.NetworkXUnbounded("Negative cycle detected.")
2029 if len(G) == 1:
2030 return {source: None}, {source: 0}
2032 G_succ = G._adj # For speed-up (and works for both directed and undirected graphs)
2034 inf = float("inf")
2035 d = {u: inf for u in G}
2036 d[source] = 0
2037 pred = {source: None}
2039 def topo_sort(relabeled):
2040 """Topologically sort nodes relabeled in the previous round and detect
2041 negative cycles.
2042 """
2043 # List of nodes to scan in this round. Denoted by A in Goldberg and
2044 # Radzik's paper.
2045 to_scan = []
2046 # In the DFS in the loop below, neg_count records for each node the
2047 # number of edges of negative reduced costs on the path from a DFS root
2048 # to the node in the DFS forest. The reduced cost of an edge (u, v) is
2049 # defined as d[u] + weight[u][v] - d[v].
2050 #
2051 # neg_count also doubles as the DFS visit marker array.
2052 neg_count = {}
2053 for u in relabeled:
2054 # Skip visited nodes.
2055 if u in neg_count:
2056 continue
2057 d_u = d[u]
2058 # Skip nodes without out-edges of negative reduced costs.
2059 if all(d_u + weight(u, v, e) >= d[v] for v, e in G_succ[u].items()):
2060 continue
2061 # Nonrecursive DFS that inserts nodes reachable from u via edges of
2062 # nonpositive reduced costs into to_scan in (reverse) topological
2063 # order.
2064 stack = [(u, iter(G_succ[u].items()))]
2065 in_stack = {u}
2066 neg_count[u] = 0
2067 while stack:
2068 u, it = stack[-1]
2069 try:
2070 v, e = next(it)
2071 except StopIteration:
2072 to_scan.append(u)
2073 stack.pop()
2074 in_stack.remove(u)
2075 continue
2076 t = d[u] + weight(u, v, e)
2077 d_v = d[v]
2078 if t < d_v:
2079 is_neg = t < d_v
2080 d[v] = t
2081 pred[v] = u
2082 if v not in neg_count:
2083 neg_count[v] = neg_count[u] + int(is_neg)
2084 stack.append((v, iter(G_succ[v].items())))
2085 in_stack.add(v)
2086 elif v in in_stack and neg_count[u] + int(is_neg) > neg_count[v]:
2087 # (u, v) is a back edge, and the cycle formed by the
2088 # path v to u and (u, v) contains at least one edge of
2089 # negative reduced cost. The cycle must be of negative
2090 # cost.
2091 raise nx.NetworkXUnbounded("Negative cycle detected.")
2092 to_scan.reverse()
2093 return to_scan
2095 def relax(to_scan):
2096 """Relax out-edges of relabeled nodes."""
2097 relabeled = set()
2098 # Scan nodes in to_scan in topological order and relax incident
2099 # out-edges. Add the relabled nodes to labeled.
2100 for u in to_scan:
2101 d_u = d[u]
2102 for v, e in G_succ[u].items():
2103 w_e = weight(u, v, e)
2104 if d_u + w_e < d[v]:
2105 d[v] = d_u + w_e
2106 pred[v] = u
2107 relabeled.add(v)
2108 return relabeled
2110 # Set of nodes relabled in the last round of scan operations. Denoted by B
2111 # in Goldberg and Radzik's paper.
2112 relabeled = {source}
2114 while relabeled:
2115 to_scan = topo_sort(relabeled)
2116 relabeled = relax(to_scan)
2118 d = {u: d[u] for u in pred}
2119 return pred, d
2122@nx._dispatch(edge_attrs="weight")
2123def negative_edge_cycle(G, weight="weight", heuristic=True):
2124 """Returns True if there exists a negative edge cycle anywhere in G.
2126 Parameters
2127 ----------
2128 G : NetworkX graph
2130 weight : string or function
2131 If this is a string, then edge weights will be accessed via the
2132 edge attribute with this key (that is, the weight of the edge
2133 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
2134 such edge attribute exists, the weight of the edge is assumed to
2135 be one.
2137 If this is a function, the weight of an edge is the value
2138 returned by the function. The function must accept exactly three
2139 positional arguments: the two endpoints of an edge and the
2140 dictionary of edge attributes for that edge. The function must
2141 return a number.
2143 heuristic : bool
2144 Determines whether to use a heuristic to early detect negative
2145 cycles at a negligible cost. In case of graphs with a negative cycle,
2146 the performance of detection increases by at least an order of magnitude.
2148 Returns
2149 -------
2150 negative_cycle : bool
2151 True if a negative edge cycle exists, otherwise False.
2153 Examples
2154 --------
2155 >>> G = nx.cycle_graph(5, create_using=nx.DiGraph())
2156 >>> print(nx.negative_edge_cycle(G))
2157 False
2158 >>> G[1][2]["weight"] = -7
2159 >>> print(nx.negative_edge_cycle(G))
2160 True
2162 Notes
2163 -----
2164 Edge weight attributes must be numerical.
2165 Distances are calculated as sums of weighted edges traversed.
2167 This algorithm uses bellman_ford_predecessor_and_distance() but finds
2168 negative cycles on any component by first adding a new node connected to
2169 every node, and starting bellman_ford_predecessor_and_distance on that
2170 node. It then removes that extra node.
2171 """
2172 if G.size() == 0:
2173 return False
2175 # find unused node to use temporarily
2176 newnode = -1
2177 while newnode in G:
2178 newnode -= 1
2179 # connect it to all nodes
2180 G.add_edges_from([(newnode, n) for n in G])
2182 try:
2183 bellman_ford_predecessor_and_distance(
2184 G, newnode, weight=weight, heuristic=heuristic
2185 )
2186 except nx.NetworkXUnbounded:
2187 return True
2188 finally:
2189 G.remove_node(newnode)
2190 return False
2193@nx._dispatch(edge_attrs="weight")
2194def find_negative_cycle(G, source, weight="weight"):
2195 """Returns a cycle with negative total weight if it exists.
2197 Bellman-Ford is used to find shortest_paths. That algorithm
2198 stops if there exists a negative cycle. This algorithm
2199 picks up from there and returns the found negative cycle.
2201 The cycle consists of a list of nodes in the cycle order. The last
2202 node equals the first to make it a cycle.
2203 You can look up the edge weights in the original graph. In the case
2204 of multigraphs the relevant edge is the minimal weight edge between
2205 the nodes in the 2-tuple.
2207 If the graph has no negative cycle, a NetworkXError is raised.
2209 Parameters
2210 ----------
2211 G : NetworkX graph
2213 source: node label
2214 The search for the negative cycle will start from this node.
2216 weight : string or function
2217 If this is a string, then edge weights will be accessed via the
2218 edge attribute with this key (that is, the weight of the edge
2219 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
2220 such edge attribute exists, the weight of the edge is assumed to
2221 be one.
2223 If this is a function, the weight of an edge is the value
2224 returned by the function. The function must accept exactly three
2225 positional arguments: the two endpoints of an edge and the
2226 dictionary of edge attributes for that edge. The function must
2227 return a number.
2229 Examples
2230 --------
2231 >>> G = nx.DiGraph()
2232 >>> G.add_weighted_edges_from([(0, 1, 2), (1, 2, 2), (2, 0, 1), (1, 4, 2), (4, 0, -5)])
2233 >>> nx.find_negative_cycle(G, 0)
2234 [4, 0, 1, 4]
2236 Returns
2237 -------
2238 cycle : list
2239 A list of nodes in the order of the cycle found. The last node
2240 equals the first to indicate a cycle.
2242 Raises
2243 ------
2244 NetworkXError
2245 If no negative cycle is found.
2246 """
2247 weight = _weight_function(G, weight)
2248 pred = {source: []}
2250 v = _inner_bellman_ford(G, [source], weight, pred=pred)
2251 if v is None:
2252 raise nx.NetworkXError("No negative cycles detected.")
2254 # negative cycle detected... find it
2255 neg_cycle = []
2256 stack = [(v, list(pred[v]))]
2257 seen = {v}
2258 while stack:
2259 node, preds = stack[-1]
2260 if v in preds:
2261 # found the cycle
2262 neg_cycle.extend([node, v])
2263 neg_cycle = list(reversed(neg_cycle))
2264 return neg_cycle
2266 if preds:
2267 nbr = preds.pop()
2268 if nbr not in seen:
2269 stack.append((nbr, list(pred[nbr])))
2270 neg_cycle.append(node)
2271 seen.add(nbr)
2272 else:
2273 stack.pop()
2274 if neg_cycle:
2275 neg_cycle.pop()
2276 else:
2277 if v in G[v] and weight(G, v, v) < 0:
2278 return [v, v]
2279 # should not reach here
2280 raise nx.NetworkXError("Negative cycle is detected but not found")
2281 # should not get here...
2282 msg = "negative cycle detected but not identified"
2283 raise nx.NetworkXUnbounded(msg)
2286@nx._dispatch(edge_attrs="weight")
2287def bidirectional_dijkstra(G, source, target, weight="weight"):
2288 r"""Dijkstra's algorithm for shortest paths using bidirectional search.
2290 Parameters
2291 ----------
2292 G : NetworkX graph
2294 source : node
2295 Starting node.
2297 target : node
2298 Ending node.
2300 weight : string or function
2301 If this is a string, then edge weights will be accessed via the
2302 edge attribute with this key (that is, the weight of the edge
2303 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
2304 such edge attribute exists, the weight of the edge is assumed to
2305 be one.
2307 If this is a function, the weight of an edge is the value
2308 returned by the function. The function must accept exactly three
2309 positional arguments: the two endpoints of an edge and the
2310 dictionary of edge attributes for that edge. The function must
2311 return a number or None to indicate a hidden edge.
2313 Returns
2314 -------
2315 length, path : number and list
2316 length is the distance from source to target.
2317 path is a list of nodes on a path from source to target.
2319 Raises
2320 ------
2321 NodeNotFound
2322 If either `source` or `target` is not in `G`.
2324 NetworkXNoPath
2325 If no path exists between source and target.
2327 Examples
2328 --------
2329 >>> G = nx.path_graph(5)
2330 >>> length, path = nx.bidirectional_dijkstra(G, 0, 4)
2331 >>> print(length)
2332 4
2333 >>> print(path)
2334 [0, 1, 2, 3, 4]
2336 Notes
2337 -----
2338 Edge weight attributes must be numerical.
2339 Distances are calculated as sums of weighted edges traversed.
2341 The weight function can be used to hide edges by returning None.
2342 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
2343 will find the shortest red path.
2345 In practice bidirectional Dijkstra is much more than twice as fast as
2346 ordinary Dijkstra.
2348 Ordinary Dijkstra expands nodes in a sphere-like manner from the
2349 source. The radius of this sphere will eventually be the length
2350 of the shortest path. Bidirectional Dijkstra will expand nodes
2351 from both the source and the target, making two spheres of half
2352 this radius. Volume of the first sphere is `\pi*r*r` while the
2353 others are `2*\pi*r/2*r/2`, making up half the volume.
2355 This algorithm is not guaranteed to work if edge weights
2356 are negative or are floating point numbers
2357 (overflows and roundoff errors can cause problems).
2359 See Also
2360 --------
2361 shortest_path
2362 shortest_path_length
2363 """
2364 if source not in G or target not in G:
2365 msg = f"Either source {source} or target {target} is not in G"
2366 raise nx.NodeNotFound(msg)
2368 if source == target:
2369 return (0, [source])
2371 weight = _weight_function(G, weight)
2372 push = heappush
2373 pop = heappop
2374 # Init: [Forward, Backward]
2375 dists = [{}, {}] # dictionary of final distances
2376 paths = [{source: [source]}, {target: [target]}] # dictionary of paths
2377 fringe = [[], []] # heap of (distance, node) for choosing node to expand
2378 seen = [{source: 0}, {target: 0}] # dict of distances to seen nodes
2379 c = count()
2380 # initialize fringe heap
2381 push(fringe[0], (0, next(c), source))
2382 push(fringe[1], (0, next(c), target))
2383 # neighs for extracting correct neighbor information
2384 if G.is_directed():
2385 neighs = [G._succ, G._pred]
2386 else:
2387 neighs = [G._adj, G._adj]
2388 # variables to hold shortest discovered path
2389 # finaldist = 1e30000
2390 finalpath = []
2391 dir = 1
2392 while fringe[0] and fringe[1]:
2393 # choose direction
2394 # dir == 0 is forward direction and dir == 1 is back
2395 dir = 1 - dir
2396 # extract closest to expand
2397 (dist, _, v) = pop(fringe[dir])
2398 if v in dists[dir]:
2399 # Shortest path to v has already been found
2400 continue
2401 # update distance
2402 dists[dir][v] = dist # equal to seen[dir][v]
2403 if v in dists[1 - dir]:
2404 # if we have scanned v in both directions we are done
2405 # we have now discovered the shortest path
2406 return (finaldist, finalpath)
2408 for w, d in neighs[dir][v].items():
2409 # weight(v, w, d) for forward and weight(w, v, d) for back direction
2410 cost = weight(v, w, d) if dir == 0 else weight(w, v, d)
2411 if cost is None:
2412 continue
2413 vwLength = dists[dir][v] + cost
2414 if w in dists[dir]:
2415 if vwLength < dists[dir][w]:
2416 raise ValueError("Contradictory paths found: negative weights?")
2417 elif w not in seen[dir] or vwLength < seen[dir][w]:
2418 # relaxing
2419 seen[dir][w] = vwLength
2420 push(fringe[dir], (vwLength, next(c), w))
2421 paths[dir][w] = paths[dir][v] + [w]
2422 if w in seen[0] and w in seen[1]:
2423 # see if this path is better than the already
2424 # discovered shortest path
2425 totaldist = seen[0][w] + seen[1][w]
2426 if finalpath == [] or finaldist > totaldist:
2427 finaldist = totaldist
2428 revpath = paths[1][w][:]
2429 revpath.reverse()
2430 finalpath = paths[0][w] + revpath[1:]
2431 raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
2434@nx._dispatch(edge_attrs="weight")
2435def johnson(G, weight="weight"):
2436 r"""Uses Johnson's Algorithm to compute shortest paths.
2438 Johnson's Algorithm finds a shortest path between each pair of
2439 nodes in a weighted graph even if negative weights are present.
2441 Parameters
2442 ----------
2443 G : NetworkX graph
2445 weight : string or function
2446 If this is a string, then edge weights will be accessed via the
2447 edge attribute with this key (that is, the weight of the edge
2448 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
2449 such edge attribute exists, the weight of the edge is assumed to
2450 be one.
2452 If this is a function, the weight of an edge is the value
2453 returned by the function. The function must accept exactly three
2454 positional arguments: the two endpoints of an edge and the
2455 dictionary of edge attributes for that edge. The function must
2456 return a number.
2458 Returns
2459 -------
2460 distance : dictionary
2461 Dictionary, keyed by source and target, of shortest paths.
2463 Examples
2464 --------
2465 >>> graph = nx.DiGraph()
2466 >>> graph.add_weighted_edges_from(
2467 ... [("0", "3", 3), ("0", "1", -5), ("0", "2", 2), ("1", "2", 4), ("2", "3", 1)]
2468 ... )
2469 >>> paths = nx.johnson(graph, weight="weight")
2470 >>> paths["0"]["2"]
2471 ['0', '1', '2']
2473 Notes
2474 -----
2475 Johnson's algorithm is suitable even for graphs with negative weights. It
2476 works by using the Bellman–Ford algorithm to compute a transformation of
2477 the input graph that removes all negative weights, allowing Dijkstra's
2478 algorithm to be used on the transformed graph.
2480 The time complexity of this algorithm is $O(n^2 \log n + n m)$,
2481 where $n$ is the number of nodes and $m$ the number of edges in the
2482 graph. For dense graphs, this may be faster than the Floyd–Warshall
2483 algorithm.
2485 See Also
2486 --------
2487 floyd_warshall_predecessor_and_distance
2488 floyd_warshall_numpy
2489 all_pairs_shortest_path
2490 all_pairs_shortest_path_length
2491 all_pairs_dijkstra_path
2492 bellman_ford_predecessor_and_distance
2493 all_pairs_bellman_ford_path
2494 all_pairs_bellman_ford_path_length
2496 """
2497 dist = {v: 0 for v in G}
2498 pred = {v: [] for v in G}
2499 weight = _weight_function(G, weight)
2501 # Calculate distance of shortest paths
2502 dist_bellman = _bellman_ford(G, list(G), weight, pred=pred, dist=dist)
2504 # Update the weight function to take into account the Bellman--Ford
2505 # relaxation distances.
2506 def new_weight(u, v, d):
2507 return weight(u, v, d) + dist_bellman[u] - dist_bellman[v]
2509 def dist_path(v):
2510 paths = {v: [v]}
2511 _dijkstra(G, v, new_weight, paths=paths)
2512 return paths
2514 return {v: dist_path(v) for v in G}