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"""
2Shortest path algorithms for weighted graphs.
3"""
5from collections import deque
6from heapq import heappop, heappush
7from itertools import count, islice
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._dispatchable(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(
137 ... (u, v, min(G[u][v], key=lambda k: G[u][v][k].get("weight", 1)))
138 ... for u, v in edges
139 ... )
140 [(1, 2, 1), (2, 3, 0)]
142 Notes
143 -----
144 Edge weight attributes must be numerical.
145 Distances are calculated as sums of weighted edges traversed.
147 The weight function can be used to hide edges by returning None.
148 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
149 will find the shortest red path.
151 The weight function can be used to include node weights.
153 >>> def func(u, v, d):
154 ... node_u_wt = G.nodes[u].get("node_weight", 1)
155 ... node_v_wt = G.nodes[v].get("node_weight", 1)
156 ... edge_wt = d.get("weight", 1)
157 ... return node_u_wt / 2 + node_v_wt / 2 + edge_wt
159 In this example we take the average of start and end node
160 weights of an edge and add it to the weight of the edge.
162 The function :func:`single_source_dijkstra` computes both
163 path and length-of-path if you need both, use that.
165 See Also
166 --------
167 bidirectional_dijkstra
168 bellman_ford_path
169 single_source_dijkstra
170 """
171 (length, path) = single_source_dijkstra(G, source, target=target, weight=weight)
172 return path
175@nx._dispatchable(edge_attrs="weight")
176def dijkstra_path_length(G, source, target, weight="weight"):
177 """Returns the shortest weighted path length in G from source to target.
179 Uses Dijkstra's Method to compute the shortest weighted path length
180 between two nodes in a graph.
182 Parameters
183 ----------
184 G : NetworkX graph
186 source : node label
187 starting node for path
189 target : node label
190 ending node for path
192 weight : string or function
193 If this is a string, then edge weights will be accessed via the
194 edge attribute with this key (that is, the weight of the edge
195 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
196 such edge attribute exists, the weight of the edge is assumed to
197 be one.
199 If this is a function, the weight of an edge is the value
200 returned by the function. The function must accept exactly three
201 positional arguments: the two endpoints of an edge and the
202 dictionary of edge attributes for that edge. The function must
203 return a number or None to indicate a hidden edge.
205 Returns
206 -------
207 length : number
208 Shortest path length.
210 Raises
211 ------
212 NodeNotFound
213 If `source` is not in `G`.
215 NetworkXNoPath
216 If no path exists between source and target.
218 Examples
219 --------
220 >>> G = nx.path_graph(5)
221 >>> nx.dijkstra_path_length(G, 0, 4)
222 4
224 Notes
225 -----
226 Edge weight attributes must be numerical.
227 Distances are calculated as sums of weighted edges traversed.
229 The weight function can be used to hide edges by returning None.
230 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
231 will find the shortest red path.
233 The function :func:`single_source_dijkstra` computes both
234 path and length-of-path if you need both, use that.
236 See Also
237 --------
238 bidirectional_dijkstra
239 bellman_ford_path_length
240 single_source_dijkstra
242 """
243 if source not in G:
244 raise nx.NodeNotFound(f"Node {source} not found in graph")
245 if source == target:
246 return 0
247 weight = _weight_function(G, weight)
248 length = _dijkstra(G, source, weight, target=target)
249 try:
250 return length[target]
251 except KeyError as err:
252 raise nx.NetworkXNoPath(f"Node {target} not reachable from {source}") from err
255@nx._dispatchable(edge_attrs="weight")
256def single_source_dijkstra_path(G, source, cutoff=None, weight="weight"):
257 """Find shortest weighted paths in G from a source node.
259 Compute shortest path between source and all other reachable
260 nodes for a weighted graph.
262 Parameters
263 ----------
264 G : NetworkX graph
266 source : node
267 Starting node for path.
269 cutoff : integer or float, optional
270 Length (sum of edge weights) at which the search is stopped.
271 If cutoff is provided, only return paths with summed weight <= cutoff.
273 weight : string or function
274 If this is a string, then edge weights will be accessed via the
275 edge attribute with this key (that is, the weight of the edge
276 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
277 such edge attribute exists, the weight of the edge is assumed to
278 be one.
280 If this is a function, the weight of an edge is the value
281 returned by the function. The function must accept exactly three
282 positional arguments: the two endpoints of an edge and the
283 dictionary of edge attributes for that edge. The function must
284 return a number or None to indicate a hidden edge.
286 Returns
287 -------
288 paths : dictionary
289 Dictionary of shortest path lengths keyed by target.
291 Raises
292 ------
293 NodeNotFound
294 If `source` is not in `G`.
296 Examples
297 --------
298 >>> G = nx.path_graph(5)
299 >>> path = nx.single_source_dijkstra_path(G, 0)
300 >>> path[4]
301 [0, 1, 2, 3, 4]
303 Notes
304 -----
305 Edge weight attributes must be numerical.
306 Distances are calculated as sums of weighted edges traversed.
308 The weight function can be used to hide edges by returning None.
309 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
310 will find the shortest red path.
312 See Also
313 --------
314 single_source_dijkstra, single_source_bellman_ford
316 """
317 return multi_source_dijkstra_path(G, {source}, cutoff=cutoff, weight=weight)
320@nx._dispatchable(edge_attrs="weight")
321def single_source_dijkstra_path_length(G, source, cutoff=None, weight="weight"):
322 """Find shortest weighted path lengths in G from a source node.
324 Compute the shortest path length between source and all other
325 reachable nodes for a weighted graph.
327 Parameters
328 ----------
329 G : NetworkX graph
331 source : node label
332 Starting node for path
334 cutoff : integer or float, optional
335 Length (sum of edge weights) at which the search is stopped.
336 If cutoff is provided, only return paths with summed weight <= cutoff.
338 weight : string or function
339 If this is a string, then edge weights will be accessed via the
340 edge attribute with this key (that is, the weight of the edge
341 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
342 such edge attribute exists, the weight of the edge is assumed to
343 be one.
345 If this is a function, the weight of an edge is the value
346 returned by the function. The function must accept exactly three
347 positional arguments: the two endpoints of an edge and the
348 dictionary of edge attributes for that edge. The function must
349 return a number or None to indicate a hidden edge.
351 Returns
352 -------
353 length : dict
354 Dict keyed by node to shortest path length from source.
356 Raises
357 ------
358 NodeNotFound
359 If `source` is not in `G`.
361 Examples
362 --------
363 >>> G = nx.path_graph(5)
364 >>> length = nx.single_source_dijkstra_path_length(G, 0)
365 >>> length[4]
366 4
367 >>> for node in [0, 1, 2, 3, 4]:
368 ... print(f"{node}: {length[node]}")
369 0: 0
370 1: 1
371 2: 2
372 3: 3
373 4: 4
375 Notes
376 -----
377 Edge weight attributes must be numerical.
378 Distances are calculated as sums of weighted edges traversed.
380 The weight function can be used to hide edges by returning None.
381 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
382 will find the shortest red path.
384 See Also
385 --------
386 single_source_dijkstra, single_source_bellman_ford_path_length
388 """
389 return multi_source_dijkstra_path_length(G, {source}, cutoff=cutoff, weight=weight)
392@nx._dispatchable(edge_attrs="weight")
393def single_source_dijkstra(G, source, target=None, cutoff=None, weight="weight"):
394 """Find shortest weighted paths and lengths from a source node.
396 Compute the shortest path length between source and all other
397 reachable nodes for a weighted graph.
399 Uses Dijkstra's algorithm to compute shortest paths and lengths
400 between a source and all other reachable nodes in a weighted graph.
402 Parameters
403 ----------
404 G : NetworkX graph
406 source : node label
407 Starting node for path
409 target : node label, optional
410 Ending node for path
412 cutoff : integer or float, optional
413 Length (sum of edge weights) at which the search is stopped.
414 If cutoff is provided, only return paths with summed weight <= cutoff.
417 weight : string or function
418 If this is a string, then edge weights will be accessed via the
419 edge attribute with this key (that is, the weight of the edge
420 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
421 such edge attribute exists, the weight of the edge is assumed to
422 be one.
424 If this is a function, the weight of an edge is the value
425 returned by the function. The function must accept exactly three
426 positional arguments: the two endpoints of an edge and the
427 dictionary of edge attributes for that edge. The function must
428 return a number or None to indicate a hidden edge.
430 Returns
431 -------
432 distance, path : pair of dictionaries, or numeric and list.
433 If target is None, paths and lengths to all nodes are computed.
434 The return value is a tuple of two dictionaries keyed by target nodes.
435 The first dictionary stores distance to each target node.
436 The second stores the path to each target node.
437 If target is not None, returns a tuple (distance, path), where
438 distance is the distance from source to target and path is a list
439 representing the path from source to target.
441 Raises
442 ------
443 NodeNotFound
444 If `source` is not in `G`.
446 Examples
447 --------
448 >>> G = nx.path_graph(5)
449 >>> length, path = nx.single_source_dijkstra(G, 0)
450 >>> length[4]
451 4
452 >>> for node in [0, 1, 2, 3, 4]:
453 ... print(f"{node}: {length[node]}")
454 0: 0
455 1: 1
456 2: 2
457 3: 3
458 4: 4
459 >>> path[4]
460 [0, 1, 2, 3, 4]
461 >>> length, path = nx.single_source_dijkstra(G, 0, 1)
462 >>> length
463 1
464 >>> path
465 [0, 1]
467 Notes
468 -----
469 Edge weight attributes must be numerical.
470 Distances are calculated as sums of weighted edges traversed.
472 The weight function can be used to hide edges by returning None.
473 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
474 will find the shortest red path.
476 Based on the Python cookbook recipe (119466) at
477 https://code.activestate.com/recipes/119466/
479 This algorithm is not guaranteed to work if edge weights
480 are negative or are floating point numbers
481 (overflows and roundoff errors can cause problems).
483 See Also
484 --------
485 single_source_dijkstra_path
486 single_source_dijkstra_path_length
487 single_source_bellman_ford
488 """
489 return multi_source_dijkstra(
490 G, {source}, cutoff=cutoff, target=target, weight=weight
491 )
494@nx._dispatchable(edge_attrs="weight")
495def multi_source_dijkstra_path(G, sources, cutoff=None, weight="weight"):
496 """Find shortest weighted paths in G from a given set of source
497 nodes.
499 Compute shortest path between any of the source nodes and all other
500 reachable nodes for a weighted graph.
502 Parameters
503 ----------
504 G : NetworkX graph
506 sources : non-empty set of nodes
507 Starting nodes for paths. If this is just a set containing a
508 single node, then all paths computed by this function will start
509 from that node. If there are two or more nodes in the set, the
510 computed paths may begin from any one of the start nodes.
512 cutoff : integer or float, optional
513 Length (sum of edge weights) at which the search is stopped.
514 If cutoff is provided, only return paths with summed weight <= cutoff.
516 weight : string or function
517 If this is a string, then edge weights will be accessed via the
518 edge attribute with this key (that is, the weight of the edge
519 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
520 such edge attribute exists, the weight of the edge is assumed to
521 be one.
523 If this is a function, the weight of an edge is the value
524 returned by the function. The function must accept exactly three
525 positional arguments: the two endpoints of an edge and the
526 dictionary of edge attributes for that edge. The function must
527 return a number or None to indicate a hidden edge.
529 Returns
530 -------
531 paths : dictionary
532 Dictionary of shortest paths keyed by target.
534 Examples
535 --------
536 >>> G = nx.path_graph(5)
537 >>> path = nx.multi_source_dijkstra_path(G, {0, 4})
538 >>> path[1]
539 [0, 1]
540 >>> path[3]
541 [4, 3]
543 Notes
544 -----
545 Edge weight attributes must be numerical.
546 Distances are calculated as sums of weighted edges traversed.
548 The weight function can be used to hide edges by returning None.
549 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
550 will find the shortest red path.
552 Raises
553 ------
554 ValueError
555 If `sources` is empty.
556 NodeNotFound
557 If any of `sources` is not in `G`.
559 See Also
560 --------
561 multi_source_dijkstra, multi_source_bellman_ford
563 """
564 length, path = multi_source_dijkstra(G, sources, cutoff=cutoff, weight=weight)
565 return path
568@nx._dispatchable(edge_attrs="weight")
569def multi_source_dijkstra_path_length(G, sources, cutoff=None, weight="weight"):
570 """Find shortest weighted path lengths in G from a given set of
571 source nodes.
573 Compute the shortest path length between any of the source nodes and
574 all other reachable nodes for a weighted graph.
576 Parameters
577 ----------
578 G : NetworkX graph
580 sources : non-empty set of nodes
581 Starting nodes for paths. If this is just a set containing a
582 single node, then all paths computed by this function will start
583 from that node. If there are two or more nodes in the set, the
584 computed paths may begin from any one of the start nodes.
586 cutoff : integer or float, optional
587 Length (sum of edge weights) at which the search is stopped.
588 If cutoff is provided, only return paths with summed weight <= cutoff.
590 weight : string or function
591 If this is a string, then edge weights will be accessed via the
592 edge attribute with this key (that is, the weight of the edge
593 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
594 such edge attribute exists, the weight of the edge is assumed to
595 be one.
597 If this is a function, the weight of an edge is the value
598 returned by the function. The function must accept exactly three
599 positional arguments: the two endpoints of an edge and the
600 dictionary of edge attributes for that edge. The function must
601 return a number or None to indicate a hidden edge.
603 Returns
604 -------
605 length : dict
606 Dict keyed by node to shortest path length to nearest source.
608 Examples
609 --------
610 >>> G = nx.path_graph(5)
611 >>> length = nx.multi_source_dijkstra_path_length(G, {0, 4})
612 >>> for node in [0, 1, 2, 3, 4]:
613 ... print(f"{node}: {length[node]}")
614 0: 0
615 1: 1
616 2: 2
617 3: 1
618 4: 0
620 Notes
621 -----
622 Edge weight attributes must be numerical.
623 Distances are calculated as sums of weighted edges traversed.
625 The weight function can be used to hide edges by returning None.
626 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
627 will find the shortest red path.
629 Raises
630 ------
631 ValueError
632 If `sources` is empty.
633 NodeNotFound
634 If any of `sources` is not in `G`.
636 See Also
637 --------
638 multi_source_dijkstra
640 """
641 if not sources:
642 raise ValueError("sources must not be empty")
643 for s in sources:
644 if s not in G:
645 raise nx.NodeNotFound(f"Node {s} not found in graph")
646 weight = _weight_function(G, weight)
647 return _dijkstra_multisource(G, sources, weight, cutoff=cutoff)
650@nx._dispatchable(edge_attrs="weight")
651def multi_source_dijkstra(G, sources, target=None, cutoff=None, weight="weight"):
652 """Find shortest weighted paths and lengths from a given set of
653 source nodes.
655 Uses Dijkstra's algorithm to compute the shortest paths and lengths
656 between one of the source nodes and the given `target`, or all other
657 reachable nodes if not specified, for a weighted graph.
659 Parameters
660 ----------
661 G : NetworkX graph
663 sources : non-empty set of nodes
664 Starting nodes for paths. If this is just a set containing a
665 single node, then all paths computed by this function will start
666 from that node. If there are two or more nodes in the set, the
667 computed paths may begin from any one of the start nodes.
669 target : node label, optional
670 Ending node for path
672 cutoff : integer or float, optional
673 Length (sum of edge weights) at which the search is stopped.
674 If cutoff is provided, only return paths with summed weight <= cutoff.
676 weight : string or function
677 If this is a string, then edge weights will be accessed via the
678 edge attribute with this key (that is, the weight of the edge
679 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
680 such edge attribute exists, the weight of the edge is assumed to
681 be one.
683 If this is a function, the weight of an edge is the value
684 returned by the function. The function must accept exactly three
685 positional arguments: the two endpoints of an edge and the
686 dictionary of edge attributes for that edge. The function must
687 return a number or None to indicate a hidden edge.
689 Returns
690 -------
691 distance, path : pair of dictionaries, or numeric and list
692 If target is None, returns a tuple of two dictionaries keyed by node.
693 The first dictionary stores distance from one of the source nodes.
694 The second stores the path from one of the sources to that node.
695 If target is not None, returns a tuple of (distance, path) where
696 distance is the distance from source to target and path is a list
697 representing the path from source to target.
699 Examples
700 --------
701 >>> G = nx.path_graph(5)
702 >>> length, path = nx.multi_source_dijkstra(G, {0, 4})
703 >>> for node in [0, 1, 2, 3, 4]:
704 ... print(f"{node}: {length[node]}")
705 0: 0
706 1: 1
707 2: 2
708 3: 1
709 4: 0
710 >>> path[1]
711 [0, 1]
712 >>> path[3]
713 [4, 3]
715 >>> length, path = nx.multi_source_dijkstra(G, {0, 4}, 1)
716 >>> length
717 1
718 >>> path
719 [0, 1]
721 Notes
722 -----
723 Edge weight attributes must be numerical.
724 Distances are calculated as sums of weighted edges traversed.
726 The weight function can be used to hide edges by returning None.
727 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
728 will find the shortest red path.
730 Based on the Python cookbook recipe (119466) at
731 https://code.activestate.com/recipes/119466/
733 This algorithm is not guaranteed to work if edge weights
734 are negative or are floating point numbers
735 (overflows and roundoff errors can cause problems).
737 Raises
738 ------
739 ValueError
740 If `sources` is empty.
741 NodeNotFound
742 If any of `sources` is not in `G`.
744 See Also
745 --------
746 multi_source_dijkstra_path
747 multi_source_dijkstra_path_length
749 """
750 if not sources:
751 raise ValueError("sources must not be empty")
752 for s in sources:
753 if s not in G:
754 raise nx.NodeNotFound(f"Node {s} not found in graph")
755 if target in sources:
756 return (0, [target])
757 weight = _weight_function(G, weight)
758 paths = {source: [source] for source in sources} # dictionary of paths
759 dist = _dijkstra_multisource(
760 G, sources, weight, paths=paths, cutoff=cutoff, target=target
761 )
762 if target is None:
763 return (dist, paths)
764 try:
765 return (dist[target], paths[target])
766 except KeyError as err:
767 raise nx.NetworkXNoPath(f"No path to {target}.") from err
770def _dijkstra(G, source, weight, pred=None, paths=None, cutoff=None, target=None):
771 """Uses Dijkstra's algorithm to find shortest weighted paths from a
772 single source.
774 This is a convenience function for :func:`_dijkstra_multisource`
775 with all the arguments the same, except the keyword argument
776 `sources` set to ``[source]``.
778 """
779 return _dijkstra_multisource(
780 G, [source], weight, pred=pred, paths=paths, cutoff=cutoff, target=target
781 )
784def _dijkstra_multisource(
785 G, sources, weight, pred=None, paths=None, cutoff=None, target=None
786):
787 """Uses Dijkstra's algorithm to find shortest weighted paths
789 Parameters
790 ----------
791 G : NetworkX graph
793 sources : non-empty iterable of nodes
794 Starting nodes for paths. If this is just an iterable containing
795 a single node, then all paths computed by this function will
796 start from that node. If there are two or more nodes in this
797 iterable, the computed paths may begin from any one of the start
798 nodes.
800 weight: function
801 Function with (u, v, data) input that returns that edge's weight
802 or None to indicate a hidden edge
804 pred: dict of lists, optional(default=None)
805 dict to store a list of predecessors keyed by that node
806 If None, predecessors are not stored.
808 paths: dict, optional (default=None)
809 dict to store the path list from source to each node, keyed by node.
810 If None, paths are not stored.
812 target : node label, optional
813 Ending node for path. Search is halted when target is found.
815 cutoff : integer or float, optional
816 Length (sum of edge weights) at which the search is stopped.
817 If cutoff is provided, only return paths with summed weight <= cutoff.
819 Returns
820 -------
821 distance : dictionary
822 A mapping from node to shortest distance to that node from one
823 of the source nodes.
825 Raises
826 ------
827 NodeNotFound
828 If any of `sources` is not in `G`.
830 Notes
831 -----
832 The optional predecessor and path dictionaries can be accessed by
833 the caller through the original pred and paths objects passed
834 as arguments. No need to explicitly return pred or paths.
836 """
837 # If `paths` is specified, we use a temporary internal dictionary (`pred_dict`) to
838 # store predecessors, used to reconstruct paths. However, if the caller
839 # passed in a `pred` dictionary, we must compute *all* predecessors, since the caller
840 # expects the full predecessor structure.
841 pred_dict = pred if paths is None or pred is not None else {}
843 G_succ = G._adj # For speed-up (and works for both directed and undirected graphs)
845 dist = {} # dictionary of final distances
846 seen = {}
847 # fringe is heapq with 3-tuples (distance,c,node)
848 # use the count c to avoid comparing nodes (may not be able to)
849 c = count()
850 fringe = []
851 for source in sources:
852 seen[source] = 0
853 heappush(fringe, (0, next(c), source))
854 number_of_sources = len(seen)
855 while fringe:
856 (dist_v, _, v) = heappop(fringe)
857 if v in dist:
858 continue # already searched this node.
859 dist[v] = dist_v
860 if v == target:
861 break
862 for u, e in G_succ[v].items():
863 cost = weight(v, u, e)
864 if cost is None:
865 continue
866 vu_dist = dist_v + cost
867 if cutoff is not None and vu_dist > cutoff:
868 continue
869 if u in dist:
870 u_dist = dist[u]
871 if vu_dist < u_dist:
872 raise ValueError("Contradictory paths found:", "negative weights?")
873 elif pred is not None and vu_dist == u_dist:
874 # Found another shortest path to u with equal distance (including zero-weight edges).
875 # We must store *all* predecessors because `pred` was provided by the caller.
876 pred_dict[u].append(v)
877 elif u not in seen or vu_dist < seen[u]:
878 seen[u] = vu_dist
879 heappush(fringe, (vu_dist, next(c), u))
880 if pred_dict is not None:
881 pred_dict[u] = [v]
882 elif pred is not None and vu_dist == seen[u]:
883 # Found another shortest path to u
884 # We must store *all* predecessors because `pred` was provided by the caller.
885 pred_dict[u].append(v)
887 if paths is not None:
888 # Reconstruct the path from source to target using the predecessor dictionary.
889 if target is None:
890 # Since `dist` is in increasing distance order, each predecessor's path is
891 # already computed by the time we process `v`. We skip the first
892 # `number_of_sources` entries because sources already have their paths defined.
893 for v in islice(dist, number_of_sources, None):
894 # `v` must be in `pred_dict`: any node with a distance (and not a source)
895 # has a predecessor.
896 paths[v] = paths[pred_dict[v][0]] + [v]
897 else:
898 # Caller requested the path to a specific target node.
899 path = paths[target] = [target]
900 while (current_preds := pred_dict.get(path[-1])) is not None:
901 path.append(current_preds[0])
902 # The path was built in reverse order, so reverse it at the end.
903 path.reverse()
905 # The optional predecessor and path dictionaries can be accessed
906 # by the caller via the pred and paths objects passed as arguments.
907 return dist
910@nx._dispatchable(edge_attrs="weight")
911def dijkstra_predecessor_and_distance(G, source, cutoff=None, weight="weight"):
912 """Compute weighted shortest path length and predecessors.
914 Uses Dijkstra's Method to obtain the shortest weighted paths
915 and return dictionaries of predecessors for each node and
916 distance for each node from the `source`.
918 Parameters
919 ----------
920 G : NetworkX graph
922 source : node label
923 Starting node for path
925 cutoff : integer or float, optional
926 Length (sum of edge weights) at which the search is stopped.
927 If cutoff is provided, only return paths with summed weight <= cutoff.
929 weight : string or function
930 If this is a string, then edge weights will be accessed via the
931 edge attribute with this key (that is, the weight of the edge
932 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
933 such edge attribute exists, the weight of the edge is assumed to
934 be one.
936 If this is a function, the weight of an edge is the value
937 returned by the function. The function must accept exactly three
938 positional arguments: the two endpoints of an edge and the
939 dictionary of edge attributes for that edge. The function must
940 return a number or None to indicate a hidden edge.
942 Returns
943 -------
944 pred, distance : dictionaries
945 Returns two dictionaries representing a list of predecessors
946 of a node and the distance to each node.
948 Raises
949 ------
950 NodeNotFound
951 If `source` is not in `G`.
953 Notes
954 -----
955 Edge weight attributes must be numerical.
956 Distances are calculated as sums of weighted edges traversed.
958 The list of predecessors contains more than one element only when
959 there are more than one shortest paths to the key node.
961 Examples
962 --------
963 >>> G = nx.path_graph(5, create_using=nx.DiGraph())
964 >>> pred, dist = nx.dijkstra_predecessor_and_distance(G, 0)
965 >>> sorted(pred.items())
966 [(0, []), (1, [0]), (2, [1]), (3, [2]), (4, [3])]
967 >>> sorted(dist.items())
968 [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
970 >>> pred, dist = nx.dijkstra_predecessor_and_distance(G, 0, 1)
971 >>> sorted(pred.items())
972 [(0, []), (1, [0])]
973 >>> sorted(dist.items())
974 [(0, 0), (1, 1)]
975 """
976 if source not in G:
977 raise nx.NodeNotFound(f"Node {source} is not found in the graph")
978 weight = _weight_function(G, weight)
979 pred = {source: []} # dictionary of predecessors
980 return (pred, _dijkstra(G, source, weight, pred=pred, cutoff=cutoff))
983@nx._dispatchable(edge_attrs="weight")
984def all_pairs_dijkstra(G, cutoff=None, weight="weight"):
985 """Find shortest weighted paths and lengths between all nodes.
987 Parameters
988 ----------
989 G : NetworkX graph
991 cutoff : integer or float, optional
992 Length (sum of edge weights) at which the search is stopped.
993 If cutoff is provided, only return paths with summed weight <= cutoff.
995 weight : string or function
996 If this is a string, then edge weights will be accessed via the
997 edge attribute with this key (that is, the weight of the edge
998 joining `u` to `v` will be ``G.edge[u][v][weight]``). If no
999 such edge attribute exists, the weight of the edge is assumed to
1000 be one.
1002 If this is a function, the weight of an edge is the value
1003 returned by the function. The function must accept exactly three
1004 positional arguments: the two endpoints of an edge and the
1005 dictionary of edge attributes for that edge. The function must
1006 return a number or None to indicate a hidden edge.
1008 Yields
1009 ------
1010 (node, (distance, path)) : (node obj, (dict, dict))
1011 Each source node has two associated dicts. The first holds distance
1012 keyed by target and the second holds paths keyed by target.
1013 (See single_source_dijkstra for the source/target node terminology.)
1014 If desired you can apply `dict()` to this function to create a dict
1015 keyed by source node to the two dicts.
1017 Examples
1018 --------
1019 >>> G = nx.path_graph(5)
1020 >>> len_path = dict(nx.all_pairs_dijkstra(G))
1021 >>> len_path[3][0][1]
1022 2
1023 >>> for node in [0, 1, 2, 3, 4]:
1024 ... print(f"3 - {node}: {len_path[3][0][node]}")
1025 3 - 0: 3
1026 3 - 1: 2
1027 3 - 2: 1
1028 3 - 3: 0
1029 3 - 4: 1
1030 >>> len_path[3][1][1]
1031 [3, 2, 1]
1032 >>> for n, (dist, path) in nx.all_pairs_dijkstra(G):
1033 ... print(path[1])
1034 [0, 1]
1035 [1]
1036 [2, 1]
1037 [3, 2, 1]
1038 [4, 3, 2, 1]
1040 Notes
1041 -----
1042 Edge weight attributes must be numerical.
1043 Distances are calculated as sums of weighted edges traversed.
1045 The yielded dicts only have keys for reachable nodes.
1046 """
1047 for n in G:
1048 dist, path = single_source_dijkstra(G, n, cutoff=cutoff, weight=weight)
1049 yield (n, (dist, path))
1052@nx._dispatchable(edge_attrs="weight")
1053def all_pairs_dijkstra_path_length(G, cutoff=None, weight="weight"):
1054 """Compute shortest path lengths between all nodes in a weighted graph.
1056 Parameters
1057 ----------
1058 G : NetworkX graph
1060 cutoff : integer or float, optional
1061 Length (sum of edge weights) at which the search is stopped.
1062 If cutoff is provided, only return paths with summed weight <= cutoff.
1064 weight : string or function
1065 If this is a string, then edge weights will be accessed via the
1066 edge attribute with this key (that is, the weight of the edge
1067 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1068 such edge attribute exists, the weight of the edge is assumed to
1069 be one.
1071 If this is a function, the weight of an edge is the value
1072 returned by the function. The function must accept exactly three
1073 positional arguments: the two endpoints of an edge and the
1074 dictionary of edge attributes for that edge. The function must
1075 return a number or None to indicate a hidden edge.
1077 Returns
1078 -------
1079 distance : iterator
1080 (source, dictionary) iterator with dictionary keyed by target and
1081 shortest path length as the key value.
1083 Examples
1084 --------
1085 >>> G = nx.path_graph(5)
1086 >>> length = dict(nx.all_pairs_dijkstra_path_length(G))
1087 >>> for node in [0, 1, 2, 3, 4]:
1088 ... print(f"1 - {node}: {length[1][node]}")
1089 1 - 0: 1
1090 1 - 1: 0
1091 1 - 2: 1
1092 1 - 3: 2
1093 1 - 4: 3
1094 >>> length[3][2]
1095 1
1096 >>> length[2][2]
1097 0
1099 Notes
1100 -----
1101 Edge weight attributes must be numerical.
1102 Distances are calculated as sums of weighted edges traversed.
1104 The dictionary returned only has keys for reachable node pairs.
1105 """
1106 length = single_source_dijkstra_path_length
1107 for n in G:
1108 yield (n, length(G, n, cutoff=cutoff, weight=weight))
1111@nx._dispatchable(edge_attrs="weight")
1112def all_pairs_dijkstra_path(G, cutoff=None, weight="weight"):
1113 """Compute shortest paths between all nodes in a weighted graph.
1115 Parameters
1116 ----------
1117 G : NetworkX graph
1119 cutoff : integer or float, optional
1120 Length (sum of edge weights) at which the search is stopped.
1121 If cutoff is provided, only return paths with summed weight <= cutoff.
1123 weight : string or function
1124 If this is a string, then edge weights will be accessed via the
1125 edge attribute with this key (that is, the weight of the edge
1126 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1127 such edge attribute exists, the weight of the edge is assumed to
1128 be one.
1130 If this is a function, the weight of an edge is the value
1131 returned by the function. The function must accept exactly three
1132 positional arguments: the two endpoints of an edge and the
1133 dictionary of edge attributes for that edge. The function must
1134 return a number or None to indicate a hidden edge.
1136 Returns
1137 -------
1138 paths : iterator
1139 (source, dictionary) iterator with dictionary keyed by target and
1140 shortest path as the key value.
1142 Examples
1143 --------
1144 >>> G = nx.path_graph(5)
1145 >>> path = dict(nx.all_pairs_dijkstra_path(G))
1146 >>> path[0][4]
1147 [0, 1, 2, 3, 4]
1149 Notes
1150 -----
1151 Edge weight attributes must be numerical.
1152 Distances are calculated as sums of weighted edges traversed.
1154 See Also
1155 --------
1156 floyd_warshall, all_pairs_bellman_ford_path
1158 """
1159 path = single_source_dijkstra_path
1160 # TODO This can be trivially parallelized.
1161 for n in G:
1162 yield (n, path(G, n, cutoff=cutoff, weight=weight))
1165@nx._dispatchable(edge_attrs="weight")
1166def bellman_ford_predecessor_and_distance(
1167 G, source, target=None, weight="weight", heuristic=False
1168):
1169 """Compute shortest path lengths and predecessors on shortest paths
1170 in weighted graphs.
1172 The algorithm has a running time of $O(mn)$ where $n$ is the number of
1173 nodes and $m$ is the number of edges. It is slower than Dijkstra but
1174 can handle negative edge weights.
1176 If a negative cycle is detected, you can use :func:`find_negative_cycle`
1177 to return the cycle and examine it. Shortest paths are not defined when
1178 a negative cycle exists because once reached, the path can cycle forever
1179 to build up arbitrarily low weights.
1181 Parameters
1182 ----------
1183 G : NetworkX graph
1184 The algorithm works for all types of graphs, including directed
1185 graphs and multigraphs.
1187 source: node label
1188 Starting node for path
1190 target : node label, optional
1191 Ending node for path
1193 weight : string or function
1194 If this is a string, then edge weights will be accessed via the
1195 edge attribute with this key (that is, the weight of the edge
1196 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1197 such edge attribute exists, the weight of the edge is assumed to
1198 be one.
1200 If this is a function, the weight of an edge is the value
1201 returned by the function. The function must accept exactly three
1202 positional arguments: the two endpoints of an edge and the
1203 dictionary of edge attributes for that edge. The function must
1204 return a number.
1206 heuristic : bool
1207 Determines whether to use a heuristic to early detect negative
1208 cycles at a hopefully negligible cost.
1210 Returns
1211 -------
1212 pred, dist : dictionaries
1213 Returns two dictionaries keyed by node to predecessor in the
1214 path and to the distance from the source respectively.
1216 Raises
1217 ------
1218 NodeNotFound
1219 If `source` is not in `G`.
1221 NetworkXUnbounded
1222 If the (di)graph contains a negative (di)cycle, the
1223 algorithm raises an exception to indicate the presence of the
1224 negative (di)cycle. Note: any negative weight edge in an
1225 undirected graph is a negative cycle.
1227 Examples
1228 --------
1229 >>> G = nx.path_graph(5, create_using=nx.DiGraph())
1230 >>> pred, dist = nx.bellman_ford_predecessor_and_distance(G, 0)
1231 >>> sorted(pred.items())
1232 [(0, []), (1, [0]), (2, [1]), (3, [2]), (4, [3])]
1233 >>> sorted(dist.items())
1234 [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
1236 >>> pred, dist = nx.bellman_ford_predecessor_and_distance(G, 0, 1)
1237 >>> sorted(pred.items())
1238 [(0, []), (1, [0]), (2, [1]), (3, [2]), (4, [3])]
1239 >>> sorted(dist.items())
1240 [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
1242 >>> G = nx.cycle_graph(5, create_using=nx.DiGraph())
1243 >>> G[1][2]["weight"] = -7
1244 >>> nx.bellman_ford_predecessor_and_distance(G, 0)
1245 Traceback (most recent call last):
1246 ...
1247 networkx.exception.NetworkXUnbounded: Negative cycle detected.
1249 See Also
1250 --------
1251 find_negative_cycle
1253 Notes
1254 -----
1255 Edge weight attributes must be numerical.
1256 Distances are calculated as sums of weighted edges traversed.
1258 The dictionaries returned only have keys for nodes reachable from
1259 the source.
1261 In the case where the (di)graph is not connected, if a component
1262 not containing the source contains a negative (di)cycle, it
1263 will not be detected.
1265 In NetworkX v2.1 and prior, the source node had predecessor `[None]`.
1266 In NetworkX v2.2 this changed to the source node having predecessor `[]`
1267 """
1268 if source not in G:
1269 raise nx.NodeNotFound(f"Node {source} is not found in the graph")
1270 weight = _weight_function(G, weight)
1271 if G.is_multigraph():
1272 if any(
1273 weight(u, v, {k: d}) < 0
1274 for u, v, k, d in nx.selfloop_edges(G, keys=True, data=True)
1275 ):
1276 raise nx.NetworkXUnbounded("Negative cycle detected.")
1277 else:
1278 if any(weight(u, v, d) < 0 for u, v, d in nx.selfloop_edges(G, data=True)):
1279 raise nx.NetworkXUnbounded("Negative cycle detected.")
1281 dist = {source: 0}
1282 pred = {source: []}
1284 if len(G) == 1:
1285 return pred, dist
1287 weight = _weight_function(G, weight)
1289 dist = _bellman_ford(
1290 G, [source], weight, pred=pred, dist=dist, target=target, heuristic=heuristic
1291 )
1292 return (pred, dist)
1295def _bellman_ford(
1296 G,
1297 source,
1298 weight,
1299 pred=None,
1300 paths=None,
1301 dist=None,
1302 target=None,
1303 heuristic=True,
1304):
1305 """Calls relaxation loop for Bellman–Ford algorithm and builds paths
1307 This is an implementation of the SPFA variant.
1308 See https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm
1310 Parameters
1311 ----------
1312 G : NetworkX graph
1314 source: list
1315 List of source nodes. The shortest path from any of the source
1316 nodes will be found if multiple sources are provided.
1318 weight : function
1319 The weight of an edge is the value returned by the function. The
1320 function must accept exactly three positional arguments: the two
1321 endpoints of an edge and the dictionary of edge attributes for
1322 that edge. The function must return a number.
1324 pred: dict of lists, optional (default=None)
1325 dict to store a list of predecessors keyed by that node
1326 If None, predecessors are not stored
1328 paths: dict, optional (default=None)
1329 dict to store the path list from source to each node, keyed by node
1330 If None, paths are not stored
1332 dist: dict, optional (default=None)
1333 dict to store distance from source to the keyed node
1334 If None, returned dist dict contents default to 0 for every node in the
1335 source list
1337 target: node label, optional
1338 Ending node for path. Path lengths to other destinations may (and
1339 probably will) be incorrect.
1341 heuristic : bool
1342 Determines whether to use a heuristic to early detect negative
1343 cycles at a hopefully negligible cost.
1345 Returns
1346 -------
1347 dist : dict
1348 Returns a dict keyed by node to the distance from the source.
1349 Dicts for paths and pred are in the mutated input dicts by those names.
1351 Raises
1352 ------
1353 NodeNotFound
1354 If any of `source` is not in `G`.
1356 NetworkXUnbounded
1357 If the (di)graph contains a negative (di)cycle, the
1358 algorithm raises an exception to indicate the presence of the
1359 negative (di)cycle. Note: any negative weight edge in an
1360 undirected graph is a negative cycle
1361 """
1362 if pred is None:
1363 pred = {v: [] for v in source}
1365 if dist is None:
1366 dist = {v: 0 for v in source}
1368 negative_cycle_found = _inner_bellman_ford(
1369 G,
1370 source,
1371 weight,
1372 pred,
1373 dist,
1374 heuristic,
1375 )
1376 if negative_cycle_found is not None:
1377 raise nx.NetworkXUnbounded("Negative cycle detected.")
1379 if paths is not None:
1380 sources = set(source)
1381 dsts = [target] if target is not None else pred
1382 for dst in dsts:
1383 gen = _build_paths_from_predecessors(sources, dst, pred)
1384 paths[dst] = next(gen)
1386 return dist
1389def _inner_bellman_ford(
1390 G,
1391 sources,
1392 weight,
1393 pred,
1394 dist=None,
1395 heuristic=True,
1396):
1397 """Inner Relaxation loop for Bellman–Ford algorithm.
1399 This is an implementation of the SPFA variant.
1400 See https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm
1402 Parameters
1403 ----------
1404 G : NetworkX graph
1406 source: list
1407 List of source nodes. The shortest path from any of the source
1408 nodes will be found if multiple sources are provided.
1410 weight : function
1411 The weight of an edge is the value returned by the function. The
1412 function must accept exactly three positional arguments: the two
1413 endpoints of an edge and the dictionary of edge attributes for
1414 that edge. The function must return a number.
1416 pred: dict of lists
1417 dict to store a list of predecessors keyed by that node
1419 dist: dict, optional (default=None)
1420 dict to store distance from source to the keyed node
1421 If None, returned dist dict contents default to 0 for every node in the
1422 source list
1424 heuristic : bool
1425 Determines whether to use a heuristic to early detect negative
1426 cycles at a hopefully negligible cost.
1428 Returns
1429 -------
1430 node or None
1431 Return a node `v` where processing discovered a negative cycle.
1432 If no negative cycle found, return None.
1434 Raises
1435 ------
1436 NodeNotFound
1437 If any of `source` is not in `G`.
1438 """
1439 for s in sources:
1440 if s not in G:
1441 raise nx.NodeNotFound(f"Source {s} not in G")
1443 if pred is None:
1444 pred = {v: [] for v in sources}
1446 if dist is None:
1447 dist = {v: 0 for v in sources}
1449 # Heuristic Storage setup. Note: use None because nodes cannot be None
1450 nonexistent_edge = (None, None)
1451 pred_edge = {v: None for v in sources}
1452 recent_update = {v: nonexistent_edge for v in sources}
1454 G_succ = G._adj # For speed-up (and works for both directed and undirected graphs)
1455 inf = float("inf")
1456 n = len(G)
1458 count = {}
1459 q = deque(sources)
1460 in_q = set(sources)
1461 while q:
1462 u = q.popleft()
1463 in_q.remove(u)
1465 # Skip relaxations if any of the predecessors of u is in the queue.
1466 if all(pred_u not in in_q for pred_u in pred[u]):
1467 dist_u = dist[u]
1468 for v, e in G_succ[u].items():
1469 dist_v = dist_u + weight(u, v, e)
1471 if dist_v < dist.get(v, inf):
1472 # In this conditional branch we are updating the path with v.
1473 # If it happens that some earlier update also added node v
1474 # that implies the existence of a negative cycle since
1475 # after the update node v would lie on the update path twice.
1476 # The update path is stored up to one of the source nodes,
1477 # therefore u is always in the dict recent_update
1478 if heuristic:
1479 if v in recent_update[u]:
1480 # Negative cycle found!
1481 pred[v].append(u)
1482 return v
1484 # Transfer the recent update info from u to v if the
1485 # same source node is the head of the update path.
1486 # If the source node is responsible for the cost update,
1487 # then clear the history and use it instead.
1488 if v in pred_edge and pred_edge[v] == u:
1489 recent_update[v] = recent_update[u]
1490 else:
1491 recent_update[v] = (u, v)
1493 if v not in in_q:
1494 q.append(v)
1495 in_q.add(v)
1496 count_v = count.get(v, 0) + 1
1497 if count_v == n:
1498 # Negative cycle found!
1499 return v
1501 count[v] = count_v
1502 dist[v] = dist_v
1503 pred[v] = [u]
1504 pred_edge[v] = u
1506 elif dist.get(v) is not None and dist_v == dist.get(v):
1507 pred[v].append(u)
1509 # successfully found shortest_path. No negative cycles found.
1510 return None
1513@nx._dispatchable(edge_attrs="weight")
1514def bellman_ford_path(G, source, target, weight="weight"):
1515 """Returns the shortest path from source to target in a weighted graph G.
1517 Parameters
1518 ----------
1519 G : NetworkX graph
1521 source : node
1522 Starting node
1524 target : node
1525 Ending node
1527 weight : string or function (default="weight")
1528 If this is a string, then edge weights will be accessed via the
1529 edge attribute with this key (that is, the weight of the edge
1530 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1531 such edge attribute exists, the weight of the edge is assumed to
1532 be one.
1534 If this is a function, the weight of an edge is the value
1535 returned by the function. The function must accept exactly three
1536 positional arguments: the two endpoints of an edge and the
1537 dictionary of edge attributes for that edge. The function must
1538 return a number.
1540 Returns
1541 -------
1542 path : list
1543 List of nodes in a shortest path.
1545 Raises
1546 ------
1547 NodeNotFound
1548 If `source` is not in `G`.
1550 NetworkXNoPath
1551 If no path exists between source and target.
1553 Examples
1554 --------
1555 >>> G = nx.path_graph(5)
1556 >>> nx.bellman_ford_path(G, 0, 4)
1557 [0, 1, 2, 3, 4]
1559 Notes
1560 -----
1561 Edge weight attributes must be numerical.
1562 Distances are calculated as sums of weighted edges traversed.
1564 See Also
1565 --------
1566 dijkstra_path, bellman_ford_path_length
1567 """
1568 length, path = single_source_bellman_ford(G, source, target=target, weight=weight)
1569 return path
1572@nx._dispatchable(edge_attrs="weight")
1573def bellman_ford_path_length(G, source, target, weight="weight"):
1574 """Returns the shortest path length from source to target
1575 in a weighted graph.
1577 Parameters
1578 ----------
1579 G : NetworkX graph
1581 source : node label
1582 starting node for path
1584 target : node label
1585 ending node for path
1587 weight : string or function (default="weight")
1588 If this is a string, then edge weights will be accessed via the
1589 edge attribute with this key (that is, the weight of the edge
1590 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1591 such edge attribute exists, the weight of the edge is assumed to
1592 be one.
1594 If this is a function, the weight of an edge is the value
1595 returned by the function. The function must accept exactly three
1596 positional arguments: the two endpoints of an edge and the
1597 dictionary of edge attributes for that edge. The function must
1598 return a number.
1600 Returns
1601 -------
1602 length : number
1603 Shortest path length.
1605 Raises
1606 ------
1607 NodeNotFound
1608 If `source` is not in `G`.
1610 NetworkXNoPath
1611 If no path exists between source and target.
1613 Examples
1614 --------
1615 >>> G = nx.path_graph(5)
1616 >>> nx.bellman_ford_path_length(G, 0, 4)
1617 4
1619 Notes
1620 -----
1621 Edge weight attributes must be numerical.
1622 Distances are calculated as sums of weighted edges traversed.
1624 See Also
1625 --------
1626 dijkstra_path_length, bellman_ford_path
1627 """
1628 if source == target:
1629 if source not in G:
1630 raise nx.NodeNotFound(f"Node {source} not found in graph")
1631 return 0
1633 weight = _weight_function(G, weight)
1635 length = _bellman_ford(G, [source], weight, target=target)
1637 try:
1638 return length[target]
1639 except KeyError as err:
1640 raise nx.NetworkXNoPath(f"node {target} not reachable from {source}") from err
1643@nx._dispatchable(edge_attrs="weight")
1644def single_source_bellman_ford_path(G, source, weight="weight"):
1645 """Compute shortest path between source and all other reachable
1646 nodes for a weighted graph.
1648 Parameters
1649 ----------
1650 G : NetworkX graph
1652 source : node
1653 Starting node for path.
1655 weight : string or function (default="weight")
1656 If this is a string, then edge weights will be accessed via the
1657 edge attribute with this key (that is, the weight of the edge
1658 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1659 such edge attribute exists, the weight of the edge is assumed to
1660 be one.
1662 If this is a function, the weight of an edge is the value
1663 returned by the function. The function must accept exactly three
1664 positional arguments: the two endpoints of an edge and the
1665 dictionary of edge attributes for that edge. The function must
1666 return a number.
1668 Returns
1669 -------
1670 paths : dictionary
1671 Dictionary of shortest path lengths keyed by target.
1673 Raises
1674 ------
1675 NodeNotFound
1676 If `source` is not in `G`.
1678 Examples
1679 --------
1680 >>> G = nx.path_graph(5)
1681 >>> path = nx.single_source_bellman_ford_path(G, 0)
1682 >>> path[4]
1683 [0, 1, 2, 3, 4]
1685 Notes
1686 -----
1687 Edge weight attributes must be numerical.
1688 Distances are calculated as sums of weighted edges traversed.
1690 See Also
1691 --------
1692 single_source_dijkstra, single_source_bellman_ford
1694 """
1695 (length, path) = single_source_bellman_ford(G, source, weight=weight)
1696 return path
1699@nx._dispatchable(edge_attrs="weight")
1700def single_source_bellman_ford_path_length(G, source, weight="weight"):
1701 """Compute the shortest path length between source and all other
1702 reachable nodes for a weighted graph.
1704 Parameters
1705 ----------
1706 G : NetworkX graph
1708 source : node label
1709 Starting node for path
1711 weight : string or function (default="weight")
1712 If this is a string, then edge weights will be accessed via the
1713 edge attribute with this key (that is, the weight of the edge
1714 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1715 such edge attribute exists, the weight of the edge is assumed to
1716 be one.
1718 If this is a function, the weight of an edge is the value
1719 returned by the function. The function must accept exactly three
1720 positional arguments: the two endpoints of an edge and the
1721 dictionary of edge attributes for that edge. The function must
1722 return a number.
1724 Returns
1725 -------
1726 length : dictionary
1727 Dictionary of shortest path length keyed by target
1729 Raises
1730 ------
1731 NodeNotFound
1732 If `source` is not in `G`.
1734 Examples
1735 --------
1736 >>> G = nx.path_graph(5)
1737 >>> length = nx.single_source_bellman_ford_path_length(G, 0)
1738 >>> length[4]
1739 4
1740 >>> for node in [0, 1, 2, 3, 4]:
1741 ... print(f"{node}: {length[node]}")
1742 0: 0
1743 1: 1
1744 2: 2
1745 3: 3
1746 4: 4
1748 Notes
1749 -----
1750 Edge weight attributes must be numerical.
1751 Distances are calculated as sums of weighted edges traversed.
1753 See Also
1754 --------
1755 single_source_dijkstra, single_source_bellman_ford
1757 """
1758 weight = _weight_function(G, weight)
1759 return _bellman_ford(G, [source], weight)
1762@nx._dispatchable(edge_attrs="weight")
1763def single_source_bellman_ford(G, source, target=None, weight="weight"):
1764 """Compute shortest paths and lengths in a weighted graph G.
1766 Uses Bellman-Ford algorithm for shortest paths.
1768 Parameters
1769 ----------
1770 G : NetworkX graph
1772 source : node label
1773 Starting node for path
1775 target : node label, optional
1776 Ending node for path
1778 weight : string or function
1779 If this is a string, then edge weights will be accessed via the
1780 edge attribute with this key (that is, the weight of the edge
1781 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1782 such edge attribute exists, the weight of the edge is assumed to
1783 be one.
1785 If this is a function, the weight of an edge is the value
1786 returned by the function. The function must accept exactly three
1787 positional arguments: the two endpoints of an edge and the
1788 dictionary of edge attributes for that edge. The function must
1789 return a number.
1791 Returns
1792 -------
1793 distance, path : pair of dictionaries, or numeric and list
1794 If target is None, returns a tuple of two dictionaries keyed by node.
1795 The first dictionary stores distance from one of the source nodes.
1796 The second stores the path from one of the sources to that node.
1797 If target is not None, returns a tuple of (distance, path) where
1798 distance is the distance from source to target and path is a list
1799 representing the path from source to target.
1801 Raises
1802 ------
1803 NodeNotFound
1804 If `source` is not in `G`.
1806 Examples
1807 --------
1808 >>> G = nx.path_graph(5)
1809 >>> length, path = nx.single_source_bellman_ford(G, 0)
1810 >>> length[4]
1811 4
1812 >>> for node in [0, 1, 2, 3, 4]:
1813 ... print(f"{node}: {length[node]}")
1814 0: 0
1815 1: 1
1816 2: 2
1817 3: 3
1818 4: 4
1819 >>> path[4]
1820 [0, 1, 2, 3, 4]
1821 >>> length, path = nx.single_source_bellman_ford(G, 0, 1)
1822 >>> length
1823 1
1824 >>> path
1825 [0, 1]
1827 Notes
1828 -----
1829 Edge weight attributes must be numerical.
1830 Distances are calculated as sums of weighted edges traversed.
1832 See Also
1833 --------
1834 single_source_dijkstra
1835 single_source_bellman_ford_path
1836 single_source_bellman_ford_path_length
1837 """
1838 if source == target:
1839 if source not in G:
1840 raise nx.NodeNotFound(f"Node {source} is not found in the graph")
1841 return (0, [source])
1843 weight = _weight_function(G, weight)
1845 paths = {source: [source]} # dictionary of paths
1846 dist = _bellman_ford(G, [source], weight, paths=paths, target=target)
1847 if target is None:
1848 return (dist, paths)
1849 try:
1850 return (dist[target], paths[target])
1851 except KeyError as err:
1852 msg = f"Node {target} not reachable from {source}"
1853 raise nx.NetworkXNoPath(msg) from err
1856@nx._dispatchable(edge_attrs="weight")
1857def all_pairs_bellman_ford_path_length(G, weight="weight"):
1858 """Compute shortest path lengths between all nodes in a weighted graph.
1860 Parameters
1861 ----------
1862 G : NetworkX graph
1864 weight : string or function (default="weight")
1865 If this is a string, then edge weights will be accessed via the
1866 edge attribute with this key (that is, the weight of the edge
1867 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1868 such edge attribute exists, the weight of the edge is assumed to
1869 be one.
1871 If this is a function, the weight of an edge is the value
1872 returned by the function. The function must accept exactly three
1873 positional arguments: the two endpoints of an edge and the
1874 dictionary of edge attributes for that edge. The function must
1875 return a number.
1877 Returns
1878 -------
1879 distance : iterator
1880 (source, dictionary) iterator with dictionary keyed by target and
1881 shortest path length as the key value.
1883 Examples
1884 --------
1885 >>> G = nx.path_graph(5)
1886 >>> length = dict(nx.all_pairs_bellman_ford_path_length(G))
1887 >>> for node in [0, 1, 2, 3, 4]:
1888 ... print(f"1 - {node}: {length[1][node]}")
1889 1 - 0: 1
1890 1 - 1: 0
1891 1 - 2: 1
1892 1 - 3: 2
1893 1 - 4: 3
1894 >>> length[3][2]
1895 1
1896 >>> length[2][2]
1897 0
1899 Notes
1900 -----
1901 Edge weight attributes must be numerical.
1902 Distances are calculated as sums of weighted edges traversed.
1904 The dictionary returned only has keys for reachable node pairs.
1905 """
1906 length = single_source_bellman_ford_path_length
1907 for n in G:
1908 yield (n, dict(length(G, n, weight=weight)))
1911@nx._dispatchable(edge_attrs="weight")
1912def all_pairs_bellman_ford_path(G, weight="weight"):
1913 """Compute shortest paths between all nodes in a weighted graph.
1915 Parameters
1916 ----------
1917 G : NetworkX graph
1919 weight : string or function (default="weight")
1920 If this is a string, then edge weights will be accessed via the
1921 edge attribute with this key (that is, the weight of the edge
1922 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1923 such edge attribute exists, the weight of the edge is assumed to
1924 be one.
1926 If this is a function, the weight of an edge is the value
1927 returned by the function. The function must accept exactly three
1928 positional arguments: the two endpoints of an edge and the
1929 dictionary of edge attributes for that edge. The function must
1930 return a number.
1932 Returns
1933 -------
1934 paths : iterator
1935 (source, dictionary) iterator with dictionary keyed by target and
1936 shortest path as the key value.
1938 Examples
1939 --------
1940 >>> G = nx.path_graph(5)
1941 >>> path = dict(nx.all_pairs_bellman_ford_path(G))
1942 >>> path[0][4]
1943 [0, 1, 2, 3, 4]
1945 Notes
1946 -----
1947 Edge weight attributes must be numerical.
1948 Distances are calculated as sums of weighted edges traversed.
1950 See Also
1951 --------
1952 floyd_warshall, all_pairs_dijkstra_path
1954 """
1955 path = single_source_bellman_ford_path
1956 for n in G:
1957 yield (n, path(G, n, weight=weight))
1960@nx._dispatchable(edge_attrs="weight")
1961def goldberg_radzik(G, source, weight="weight"):
1962 """Compute shortest path lengths and predecessors on shortest paths
1963 in weighted graphs.
1965 The algorithm has a running time of $O(mn)$ where $n$ is the number of
1966 nodes and $m$ is the number of edges. It is slower than Dijkstra but
1967 can handle negative edge weights.
1969 Parameters
1970 ----------
1971 G : NetworkX graph
1972 The algorithm works for all types of graphs, including directed
1973 graphs and multigraphs.
1975 source: node label
1976 Starting node for path
1978 weight : string or function
1979 If this is a string, then edge weights will be accessed via the
1980 edge attribute with this key (that is, the weight of the edge
1981 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
1982 such edge attribute exists, the weight of the edge is assumed to
1983 be one.
1985 If this is a function, the weight of an edge is the value
1986 returned by the function. The function must accept exactly three
1987 positional arguments: the two endpoints of an edge and the
1988 dictionary of edge attributes for that edge. The function must
1989 return a number.
1991 Returns
1992 -------
1993 pred, dist : dictionaries
1994 Returns two dictionaries keyed by node to predecessor in the
1995 path and to the distance from the source respectively.
1997 Raises
1998 ------
1999 NodeNotFound
2000 If `source` is not in `G`.
2002 NetworkXUnbounded
2003 If the (di)graph contains a negative (di)cycle, the
2004 algorithm raises an exception to indicate the presence of the
2005 negative (di)cycle. Note: any negative weight edge in an
2006 undirected graph is a negative cycle.
2008 As of NetworkX v3.2, a zero weight cycle is no longer
2009 incorrectly reported as a negative weight cycle.
2012 Examples
2013 --------
2014 >>> G = nx.path_graph(5, create_using=nx.DiGraph())
2015 >>> pred, dist = nx.goldberg_radzik(G, 0)
2016 >>> sorted(pred.items())
2017 [(0, None), (1, 0), (2, 1), (3, 2), (4, 3)]
2018 >>> sorted(dist.items())
2019 [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]
2021 >>> G = nx.cycle_graph(5, create_using=nx.DiGraph())
2022 >>> G[1][2]["weight"] = -7
2023 >>> nx.goldberg_radzik(G, 0)
2024 Traceback (most recent call last):
2025 ...
2026 networkx.exception.NetworkXUnbounded: Negative cycle detected.
2028 Notes
2029 -----
2030 Edge weight attributes must be numerical.
2031 Distances are calculated as sums of weighted edges traversed.
2033 The dictionaries returned only have keys for nodes reachable from
2034 the source.
2036 In the case where the (di)graph is not connected, if a component
2037 not containing the source contains a negative (di)cycle, it
2038 will not be detected.
2040 """
2041 if source not in G:
2042 raise nx.NodeNotFound(f"Node {source} is not found in the graph")
2043 weight = _weight_function(G, weight)
2044 if G.is_multigraph():
2045 if any(
2046 weight(u, v, {k: d}) < 0
2047 for u, v, k, d in nx.selfloop_edges(G, keys=True, data=True)
2048 ):
2049 raise nx.NetworkXUnbounded("Negative cycle detected.")
2050 else:
2051 if any(weight(u, v, d) < 0 for u, v, d in nx.selfloop_edges(G, data=True)):
2052 raise nx.NetworkXUnbounded("Negative cycle detected.")
2054 if len(G) == 1:
2055 return {source: None}, {source: 0}
2057 G_succ = G._adj # For speed-up (and works for both directed and undirected graphs)
2059 inf = float("inf")
2060 d = {u: inf for u in G}
2061 d[source] = 0
2062 pred = {source: None}
2064 def topo_sort(relabeled):
2065 """Topologically sort nodes relabeled in the previous round and detect
2066 negative cycles.
2067 """
2068 # List of nodes to scan in this round. Denoted by A in Goldberg and
2069 # Radzik's paper.
2070 to_scan = []
2071 # In the DFS in the loop below, neg_count records for each node the
2072 # number of edges of negative reduced costs on the path from a DFS root
2073 # to the node in the DFS forest. The reduced cost of an edge (u, v) is
2074 # defined as d[u] + weight[u][v] - d[v].
2075 #
2076 # neg_count also doubles as the DFS visit marker array.
2077 neg_count = {}
2078 for u in relabeled - neg_count.keys():
2079 d_u = d[u]
2080 # Skip nodes without out-edges of negative reduced costs.
2081 if all(d_u + weight(u, v, e) >= d[v] for v, e in G_succ[u].items()):
2082 continue
2083 # Nonrecursive DFS that inserts nodes reachable from u via edges of
2084 # nonpositive reduced costs into to_scan in (reverse) topological
2085 # order.
2086 stack = [(u, iter(G_succ[u].items()))]
2087 in_stack = {u}
2088 neg_count[u] = 0
2089 while stack:
2090 u, it = stack[-1]
2091 try:
2092 v, e = next(it)
2093 except StopIteration:
2094 to_scan.append(u)
2095 stack.pop()
2096 in_stack.remove(u)
2097 continue
2098 t = d[u] + weight(u, v, e)
2099 d_v = d[v]
2100 if t < d_v:
2101 d[v] = t
2102 pred[v] = u
2103 if v not in neg_count:
2104 neg_count[v] = neg_count[u] + 1
2105 stack.append((v, iter(G_succ[v].items())))
2106 in_stack.add(v)
2107 elif v in in_stack and neg_count[u] + 1 > neg_count[v]:
2108 # (u, v) is a back edge, and the cycle formed by the
2109 # path v to u and (u, v) contains at least one edge of
2110 # negative reduced cost. The cycle must be of negative
2111 # cost.
2112 raise nx.NetworkXUnbounded("Negative cycle detected.")
2113 to_scan.reverse()
2114 return to_scan
2116 def relax(to_scan):
2117 """Relax out-edges of relabeled nodes."""
2118 relabeled = set()
2119 # Scan nodes in to_scan in topological order and relax incident
2120 # out-edges. Add the relabeled nodes to labeled.
2121 for u in to_scan:
2122 d_u = d[u]
2123 for v, e in G_succ[u].items():
2124 w_e = weight(u, v, e)
2125 if d_u + w_e < d[v]:
2126 d[v] = d_u + w_e
2127 pred[v] = u
2128 relabeled.add(v)
2129 return relabeled
2131 # Set of nodes relabeled in the last round of scan operations. Denoted by B
2132 # in Goldberg and Radzik's paper.
2133 relabeled = {source}
2135 while relabeled:
2136 to_scan = topo_sort(relabeled)
2137 relabeled = relax(to_scan)
2139 d = {u: d[u] for u in pred}
2140 return pred, d
2143@nx._dispatchable(edge_attrs="weight")
2144def negative_edge_cycle(G, weight="weight", heuristic=True):
2145 """Returns True if there exists a negative edge cycle anywhere in G.
2147 Parameters
2148 ----------
2149 G : NetworkX graph
2151 weight : string or function
2152 If this is a string, then edge weights will be accessed via the
2153 edge attribute with this key (that is, the weight of the edge
2154 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
2155 such edge attribute exists, the weight of the edge is assumed to
2156 be one.
2158 If this is a function, the weight of an edge is the value
2159 returned by the function. The function must accept exactly three
2160 positional arguments: the two endpoints of an edge and the
2161 dictionary of edge attributes for that edge. The function must
2162 return a number.
2164 heuristic : bool
2165 Determines whether to use a heuristic to early detect negative
2166 cycles at a negligible cost. In case of graphs with a negative cycle,
2167 the performance of detection increases by at least an order of magnitude.
2169 Returns
2170 -------
2171 negative_cycle : bool
2172 True if a negative edge cycle exists, otherwise False.
2174 Examples
2175 --------
2176 >>> G = nx.cycle_graph(5, create_using=nx.DiGraph())
2177 >>> print(nx.negative_edge_cycle(G))
2178 False
2179 >>> G[1][2]["weight"] = -7
2180 >>> print(nx.negative_edge_cycle(G))
2181 True
2183 Notes
2184 -----
2185 Edge weight attributes must be numerical.
2186 Distances are calculated as sums of weighted edges traversed.
2188 This algorithm uses bellman_ford_predecessor_and_distance() but finds
2189 negative cycles on any component by first adding a new node connected to
2190 every node, and starting bellman_ford_predecessor_and_distance on that
2191 node. It then removes that extra node.
2192 """
2193 if G.size() == 0:
2194 return False
2196 # find unused node to use temporarily
2197 newnode = -1
2198 while newnode in G:
2199 newnode -= 1
2200 # connect it to all nodes
2201 G.add_edges_from([(newnode, n) for n in G])
2203 try:
2204 bellman_ford_predecessor_and_distance(
2205 G, newnode, weight=weight, heuristic=heuristic
2206 )
2207 except nx.NetworkXUnbounded:
2208 return True
2209 finally:
2210 G.remove_node(newnode)
2211 return False
2214@nx._dispatchable(edge_attrs="weight")
2215def find_negative_cycle(G, source, weight="weight"):
2216 """Returns a cycle with negative total weight if it exists.
2218 Bellman-Ford is used to find shortest_paths. That algorithm
2219 stops if there exists a negative cycle. This algorithm
2220 picks up from there and returns the found negative cycle.
2222 The cycle consists of a list of nodes in the cycle order. The last
2223 node equals the first to make it a cycle.
2224 You can look up the edge weights in the original graph. In the case
2225 of multigraphs the relevant edge is the minimal weight edge between
2226 the nodes in the 2-tuple.
2228 If the graph has no negative cycle, a NetworkXError is raised.
2230 Parameters
2231 ----------
2232 G : NetworkX graph
2234 source: node label
2235 The search for the negative cycle will start from this node.
2237 weight : string or function
2238 If this is a string, then edge weights will be accessed via the
2239 edge attribute with this key (that is, the weight of the edge
2240 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
2241 such edge attribute exists, the weight of the edge is assumed to
2242 be one.
2244 If this is a function, the weight of an edge is the value
2245 returned by the function. The function must accept exactly three
2246 positional arguments: the two endpoints of an edge and the
2247 dictionary of edge attributes for that edge. The function must
2248 return a number.
2250 Examples
2251 --------
2252 >>> G = nx.DiGraph()
2253 >>> G.add_weighted_edges_from(
2254 ... [(0, 1, 2), (1, 2, 2), (2, 0, 1), (1, 4, 2), (4, 0, -5)]
2255 ... )
2256 >>> nx.find_negative_cycle(G, 0)
2257 [4, 0, 1, 4]
2259 Returns
2260 -------
2261 cycle : list
2262 A list of nodes in the order of the cycle found. The last node
2263 equals the first to indicate a cycle.
2265 Raises
2266 ------
2267 NetworkXError
2268 If no negative cycle is found.
2269 """
2270 weight = _weight_function(G, weight)
2271 pred = {source: []}
2273 v = _inner_bellman_ford(G, [source], weight, pred=pred)
2274 if v is None:
2275 raise nx.NetworkXError("No negative cycles detected.")
2277 # negative cycle detected... find it
2278 neg_cycle = []
2279 stack = [(v, list(pred[v]))]
2280 seen = {v}
2281 while stack:
2282 node, preds = stack[-1]
2283 if v in preds:
2284 # found the cycle
2285 neg_cycle.extend([node, v])
2286 neg_cycle = list(reversed(neg_cycle))
2287 return neg_cycle
2289 if preds:
2290 nbr = preds.pop()
2291 if nbr not in seen:
2292 stack.append((nbr, list(pred[nbr])))
2293 neg_cycle.append(node)
2294 seen.add(nbr)
2295 else:
2296 stack.pop()
2297 if neg_cycle:
2298 neg_cycle.pop()
2299 else:
2300 if v in G[v] and weight(G, v, v) < 0:
2301 return [v, v]
2302 # should not reach here
2303 raise nx.NetworkXError("Negative cycle is detected but not found")
2304 # should not get here...
2305 msg = "negative cycle detected but not identified"
2306 raise nx.NetworkXUnbounded(msg)
2309@nx._dispatchable(edge_attrs="weight")
2310def bidirectional_dijkstra(G, source, target, weight="weight"):
2311 r"""Dijkstra's algorithm for shortest paths using bidirectional search.
2313 Parameters
2314 ----------
2315 G : NetworkX graph
2317 source : node
2318 Starting node.
2320 target : node
2321 Ending node.
2323 weight : string or function
2324 If this is a string, then edge weights will be accessed via the
2325 edge attribute with this key (that is, the weight of the edge
2326 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
2327 such edge attribute exists, the weight of the edge is assumed to
2328 be one.
2330 If this is a function, the weight of an edge is the value
2331 returned by the function. The function must accept exactly three
2332 positional arguments: the two endpoints of an edge and the
2333 dictionary of edge attributes for that edge. The function must
2334 return a number or None to indicate a hidden edge.
2336 Returns
2337 -------
2338 length, path : number and list
2339 length is the distance from source to target.
2340 path is a list of nodes on a path from source to target.
2342 Raises
2343 ------
2344 NodeNotFound
2345 If `source` or `target` is not in `G`.
2347 NetworkXNoPath
2348 If no path exists between source and target.
2350 Examples
2351 --------
2352 >>> G = nx.path_graph(5)
2353 >>> length, path = nx.bidirectional_dijkstra(G, 0, 4)
2354 >>> print(length)
2355 4
2356 >>> print(path)
2357 [0, 1, 2, 3, 4]
2359 Notes
2360 -----
2361 Edge weight attributes must be numerical.
2362 Distances are calculated as sums of weighted edges traversed.
2364 The weight function can be used to hide edges by returning None.
2365 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
2366 will find the shortest red path.
2368 In practice bidirectional Dijkstra is much more than twice as fast as
2369 ordinary Dijkstra.
2371 Ordinary Dijkstra expands nodes in a sphere-like manner from the
2372 source. The radius of this sphere will eventually be the length
2373 of the shortest path. Bidirectional Dijkstra will expand nodes
2374 from both the source and the target, making two spheres of half
2375 this radius. Volume of the first sphere is `\pi*r*r` while the
2376 others are `2*\pi*r/2*r/2`, making up half the volume.
2378 This algorithm is not guaranteed to work if edge weights
2379 are negative or are floating point numbers
2380 (overflows and roundoff errors can cause problems).
2382 See Also
2383 --------
2384 shortest_path
2385 shortest_path_length
2386 """
2387 if source not in G:
2388 raise nx.NodeNotFound(f"Source {source} is not in G")
2390 if target not in G:
2391 raise nx.NodeNotFound(f"Target {target} is not in G")
2393 if source == target:
2394 return (0, [source])
2396 weight = _weight_function(G, weight)
2397 # Init: [Forward, Backward]
2398 dists = [{}, {}] # dictionary of final distances
2399 preds = [{source: None}, {target: None}] # dictionary of preds
2401 def path(curr, direction):
2402 ret = []
2403 while curr is not None:
2404 ret.append(curr)
2405 curr = preds[direction][curr]
2406 return list(reversed(ret)) if direction == 0 else ret
2408 fringe = [[], []] # heap of (distance, node) for choosing node to expand
2409 seen = [{source: 0}, {target: 0}] # dict of distances to seen nodes
2410 c = count()
2411 # initialize fringe heap
2412 heappush(fringe[0], (0, next(c), source))
2413 heappush(fringe[1], (0, next(c), target))
2414 # neighbors for extracting correct neighbor information
2415 if G.is_directed():
2416 neighbors = [G._succ, G._pred]
2417 else:
2418 neighbors = [G._adj, G._adj]
2419 # variables to hold shortest discovered path
2420 finaldist = None
2421 meetnode = None
2422 direction = 1
2423 while fringe[0] and fringe[1]:
2424 # choose direction
2425 # direction == 0 is forward direction and direction == 1 is back
2426 direction = 1 - direction
2427 # extract closest to expand
2428 (dist, _, v) = heappop(fringe[direction])
2429 if v in dists[direction]:
2430 # Shortest path to v has already been found
2431 continue
2432 # update distance
2433 dists[direction][v] = dist # equal to seen[direction][v]
2434 if v in dists[1 - direction]:
2435 # if we have scanned v in both directions we are done
2436 # we have now discovered the shortest path
2437 return (finaldist, path(meetnode, 0) + path(preds[1][meetnode], 1))
2439 for w, d in neighbors[direction][v].items():
2440 # weight(v, w, d) for forward and weight(w, v, d) for back direction
2441 cost = weight(v, w, d) if direction == 0 else weight(w, v, d)
2442 if cost is None:
2443 continue
2444 vwLength = dist + cost
2445 if w in dists[direction]:
2446 if vwLength < dists[direction][w]:
2447 raise ValueError("Contradictory paths found: negative weights?")
2448 elif w not in seen[direction] or vwLength < seen[direction][w]:
2449 # relaxing
2450 seen[direction][w] = vwLength
2451 heappush(fringe[direction], (vwLength, next(c), w))
2452 preds[direction][w] = v
2453 if w in seen[1 - direction]:
2454 # see if this path is better than the already
2455 # discovered shortest path
2456 finaldist_w = vwLength + seen[1 - direction][w]
2457 if finaldist is None or finaldist > finaldist_w:
2458 finaldist, meetnode = finaldist_w, w
2459 raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
2462@nx._dispatchable(edge_attrs="weight")
2463def johnson(G, weight="weight"):
2464 r"""Uses Johnson's Algorithm to compute shortest paths.
2466 Johnson's Algorithm finds a shortest path between each pair of
2467 nodes in a weighted graph even if negative weights are present.
2469 Parameters
2470 ----------
2471 G : NetworkX graph
2473 weight : string or function
2474 If this is a string, then edge weights will be accessed via the
2475 edge attribute with this key (that is, the weight of the edge
2476 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no
2477 such edge attribute exists, the weight of the edge is assumed to
2478 be one.
2480 If this is a function, the weight of an edge is the value
2481 returned by the function. The function must accept exactly three
2482 positional arguments: the two endpoints of an edge and the
2483 dictionary of edge attributes for that edge. The function must
2484 return a number.
2486 Returns
2487 -------
2488 distance : dictionary
2489 Dictionary, keyed by source and target, of shortest paths.
2491 Examples
2492 --------
2493 >>> graph = nx.DiGraph()
2494 >>> graph.add_weighted_edges_from(
2495 ... [("0", "3", 3), ("0", "1", -5), ("0", "2", 2), ("1", "2", 4), ("2", "3", 1)]
2496 ... )
2497 >>> paths = nx.johnson(graph, weight="weight")
2498 >>> paths["0"]["2"]
2499 ['0', '1', '2']
2501 Notes
2502 -----
2503 Johnson's algorithm is suitable even for graphs with negative weights. It
2504 works by using the Bellman–Ford algorithm to compute a transformation of
2505 the input graph that removes all negative weights, allowing Dijkstra's
2506 algorithm to be used on the transformed graph.
2508 The time complexity of this algorithm is $O(n^2 \log n + n m)$,
2509 where $n$ is the number of nodes and $m$ the number of edges in the
2510 graph. For dense graphs, this may be faster than the Floyd–Warshall
2511 algorithm.
2513 See Also
2514 --------
2515 floyd_warshall_predecessor_and_distance
2516 floyd_warshall_numpy
2517 all_pairs_shortest_path
2518 all_pairs_shortest_path_length
2519 all_pairs_dijkstra_path
2520 bellman_ford_predecessor_and_distance
2521 all_pairs_bellman_ford_path
2522 all_pairs_bellman_ford_path_length
2524 """
2525 dist = {v: 0 for v in G}
2526 pred = {v: [] for v in G}
2527 weight = _weight_function(G, weight)
2529 # Calculate distance of shortest paths
2530 dist_bellman = _bellman_ford(G, list(G), weight, pred=pred, dist=dist)
2532 # Update the weight function to take into account the Bellman--Ford
2533 # relaxation distances.
2534 def new_weight(u, v, d):
2535 return weight(u, v, d) + dist_bellman[u] - dist_bellman[v]
2537 def dist_path(v):
2538 paths = {v: [v]}
2539 _dijkstra(G, v, new_weight, paths=paths)
2540 return paths
2542 return {v: dist_path(v) for v in G}