Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/shortest_paths/weighted.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 Shortest path algorithms for weighed graphs. | |
3 """ | |
4 | |
5 from collections import deque | |
6 from heapq import heappush, heappop | |
7 from itertools import count | |
8 import networkx as nx | |
9 from networkx.utils import generate_unique_node | |
10 from networkx.algorithms.shortest_paths.generic import _build_paths_from_predecessors | |
11 | |
12 | |
13 __all__ = [ | |
14 "dijkstra_path", | |
15 "dijkstra_path_length", | |
16 "bidirectional_dijkstra", | |
17 "single_source_dijkstra", | |
18 "single_source_dijkstra_path", | |
19 "single_source_dijkstra_path_length", | |
20 "multi_source_dijkstra", | |
21 "multi_source_dijkstra_path", | |
22 "multi_source_dijkstra_path_length", | |
23 "all_pairs_dijkstra", | |
24 "all_pairs_dijkstra_path", | |
25 "all_pairs_dijkstra_path_length", | |
26 "dijkstra_predecessor_and_distance", | |
27 "bellman_ford_path", | |
28 "bellman_ford_path_length", | |
29 "single_source_bellman_ford", | |
30 "single_source_bellman_ford_path", | |
31 "single_source_bellman_ford_path_length", | |
32 "all_pairs_bellman_ford_path", | |
33 "all_pairs_bellman_ford_path_length", | |
34 "bellman_ford_predecessor_and_distance", | |
35 "negative_edge_cycle", | |
36 "goldberg_radzik", | |
37 "johnson", | |
38 ] | |
39 | |
40 | |
41 def _weight_function(G, weight): | |
42 """Returns a function that returns the weight of an edge. | |
43 | |
44 The returned function is specifically suitable for input to | |
45 functions :func:`_dijkstra` and :func:`_bellman_ford_relaxation`. | |
46 | |
47 Parameters | |
48 ---------- | |
49 G : NetworkX graph. | |
50 | |
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. | |
56 | |
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. | |
64 | |
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. | |
69 | |
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) | |
79 | |
80 | |
81 def dijkstra_path(G, source, target, weight="weight"): | |
82 """Returns the shortest weighted path from source to target in G. | |
83 | |
84 Uses Dijkstra's Method to compute the shortest weighted path | |
85 between two nodes in a graph. | |
86 | |
87 Parameters | |
88 ---------- | |
89 G : NetworkX graph | |
90 | |
91 source : node | |
92 Starting node | |
93 | |
94 target : node | |
95 Ending node | |
96 | |
97 weight : string or function | |
98 If this is a string, then edge weights will be accessed via the | |
99 edge attribute with this key (that is, the weight of the edge | |
100 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no | |
101 such edge attribute exists, the weight of the edge is assumed to | |
102 be one. | |
103 | |
104 If this is a function, the weight of an edge is the value | |
105 returned by the function. The function must accept exactly three | |
106 positional arguments: the two endpoints of an edge and the | |
107 dictionary of edge attributes for that edge. The function must | |
108 return a number. | |
109 | |
110 Returns | |
111 ------- | |
112 path : list | |
113 List of nodes in a shortest path. | |
114 | |
115 Raises | |
116 ------ | |
117 NodeNotFound | |
118 If `source` is not in `G`. | |
119 | |
120 NetworkXNoPath | |
121 If no path exists between source and target. | |
122 | |
123 Examples | |
124 -------- | |
125 >>> G = nx.path_graph(5) | |
126 >>> print(nx.dijkstra_path(G, 0, 4)) | |
127 [0, 1, 2, 3, 4] | |
128 | |
129 Notes | |
130 ----- | |
131 Edge weight attributes must be numerical. | |
132 Distances are calculated as sums of weighted edges traversed. | |
133 | |
134 The weight function can be used to hide edges by returning None. | |
135 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None`` | |
136 will find the shortest red path. | |
137 | |
138 The weight function can be used to include node weights. | |
139 | |
140 >>> def func(u, v, d): | |
141 ... node_u_wt = G.nodes[u].get("node_weight", 1) | |
142 ... node_v_wt = G.nodes[v].get("node_weight", 1) | |
143 ... edge_wt = d.get("weight", 1) | |
144 ... return node_u_wt / 2 + node_v_wt / 2 + edge_wt | |
145 | |
146 In this example we take the average of start and end node | |
147 weights of an edge and add it to the weight of the edge. | |
148 | |
149 The function :func:`single_source_dijkstra` computes both | |
150 path and length-of-path if you need both, use that. | |
151 | |
152 See Also | |
153 -------- | |
154 bidirectional_dijkstra(), bellman_ford_path() | |
155 single_source_dijkstra() | |
156 """ | |
157 (length, path) = single_source_dijkstra(G, source, target=target, weight=weight) | |
158 return path | |
159 | |
160 | |
161 def dijkstra_path_length(G, source, target, weight="weight"): | |
162 """Returns the shortest weighted path length in G from source to target. | |
163 | |
164 Uses Dijkstra's Method to compute the shortest weighted path length | |
165 between two nodes in a graph. | |
166 | |
167 Parameters | |
168 ---------- | |
169 G : NetworkX graph | |
170 | |
171 source : node label | |
172 starting node for path | |
173 | |
174 target : node label | |
175 ending node for path | |
176 | |
177 weight : string or function | |
178 If this is a string, then edge weights will be accessed via the | |
179 edge attribute with this key (that is, the weight of the edge | |
180 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no | |
181 such edge attribute exists, the weight of the edge is assumed to | |
182 be one. | |
183 | |
184 If this is a function, the weight of an edge is the value | |
185 returned by the function. The function must accept exactly three | |
186 positional arguments: the two endpoints of an edge and the | |
187 dictionary of edge attributes for that edge. The function must | |
188 return a number. | |
189 | |
190 Returns | |
191 ------- | |
192 length : number | |
193 Shortest path length. | |
194 | |
195 Raises | |
196 ------ | |
197 NodeNotFound | |
198 If `source` is not in `G`. | |
199 | |
200 NetworkXNoPath | |
201 If no path exists between source and target. | |
202 | |
203 Examples | |
204 -------- | |
205 >>> G = nx.path_graph(5) | |
206 >>> print(nx.dijkstra_path_length(G, 0, 4)) | |
207 4 | |
208 | |
209 Notes | |
210 ----- | |
211 Edge weight attributes must be numerical. | |
212 Distances are calculated as sums of weighted edges traversed. | |
213 | |
214 The weight function can be used to hide edges by returning None. | |
215 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None`` | |
216 will find the shortest red path. | |
217 | |
218 The function :func:`single_source_dijkstra` computes both | |
219 path and length-of-path if you need both, use that. | |
220 | |
221 See Also | |
222 -------- | |
223 bidirectional_dijkstra(), bellman_ford_path_length() | |
224 single_source_dijkstra() | |
225 | |
226 """ | |
227 if source == target: | |
228 return 0 | |
229 weight = _weight_function(G, weight) | |
230 length = _dijkstra(G, source, weight, target=target) | |
231 try: | |
232 return length[target] | |
233 except KeyError as e: | |
234 raise nx.NetworkXNoPath(f"Node {target} not reachable from {source}") from e | |
235 | |
236 | |
237 def single_source_dijkstra_path(G, source, cutoff=None, weight="weight"): | |
238 """Find shortest weighted paths in G from a source node. | |
239 | |
240 Compute shortest path between source and all other reachable | |
241 nodes for a weighted graph. | |
242 | |
243 Parameters | |
244 ---------- | |
245 G : NetworkX graph | |
246 | |
247 source : node | |
248 Starting node for path. | |
249 | |
250 cutoff : integer or float, optional | |
251 Depth to stop the search. Only return paths with length <= cutoff. | |
252 | |
253 weight : string or function | |
254 If this is a string, then edge weights will be accessed via the | |
255 edge attribute with this key (that is, the weight of the edge | |
256 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no | |
257 such edge attribute exists, the weight of the edge is assumed to | |
258 be one. | |
259 | |
260 If this is a function, the weight of an edge is the value | |
261 returned by the function. The function must accept exactly three | |
262 positional arguments: the two endpoints of an edge and the | |
263 dictionary of edge attributes for that edge. The function must | |
264 return a number. | |
265 | |
266 Returns | |
267 ------- | |
268 paths : dictionary | |
269 Dictionary of shortest path lengths keyed by target. | |
270 | |
271 Raises | |
272 ------ | |
273 NodeNotFound | |
274 If `source` is not in `G`. | |
275 | |
276 Examples | |
277 -------- | |
278 >>> G = nx.path_graph(5) | |
279 >>> path = nx.single_source_dijkstra_path(G, 0) | |
280 >>> path[4] | |
281 [0, 1, 2, 3, 4] | |
282 | |
283 Notes | |
284 ----- | |
285 Edge weight attributes must be numerical. | |
286 Distances are calculated as sums of weighted edges traversed. | |
287 | |
288 The weight function can be used to hide edges by returning None. | |
289 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None`` | |
290 will find the shortest red path. | |
291 | |
292 See Also | |
293 -------- | |
294 single_source_dijkstra(), single_source_bellman_ford() | |
295 | |
296 """ | |
297 return multi_source_dijkstra_path(G, {source}, cutoff=cutoff, weight=weight) | |
298 | |
299 | |
300 def single_source_dijkstra_path_length(G, source, cutoff=None, weight="weight"): | |
301 """Find shortest weighted path lengths in G from a source node. | |
302 | |
303 Compute the shortest path length between source and all other | |
304 reachable nodes for a weighted graph. | |
305 | |
306 Parameters | |
307 ---------- | |
308 G : NetworkX graph | |
309 | |
310 source : node label | |
311 Starting node for path | |
312 | |
313 cutoff : integer or float, optional | |
314 Depth to stop the search. Only return paths with length <= cutoff. | |
315 | |
316 weight : string or function | |
317 If this is a string, then edge weights will be accessed via the | |
318 edge attribute with this key (that is, the weight of the edge | |
319 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no | |
320 such edge attribute exists, the weight of the edge is assumed to | |
321 be one. | |
322 | |
323 If this is a function, the weight of an edge is the value | |
324 returned by the function. The function must accept exactly three | |
325 positional arguments: the two endpoints of an edge and the | |
326 dictionary of edge attributes for that edge. The function must | |
327 return a number. | |
328 | |
329 Returns | |
330 ------- | |
331 length : dict | |
332 Dict keyed by node to shortest path length from source. | |
333 | |
334 Raises | |
335 ------ | |
336 NodeNotFound | |
337 If `source` is not in `G`. | |
338 | |
339 Examples | |
340 -------- | |
341 >>> G = nx.path_graph(5) | |
342 >>> length = nx.single_source_dijkstra_path_length(G, 0) | |
343 >>> length[4] | |
344 4 | |
345 >>> for node in [0, 1, 2, 3, 4]: | |
346 ... print(f"{node}: {length[node]}") | |
347 0: 0 | |
348 1: 1 | |
349 2: 2 | |
350 3: 3 | |
351 4: 4 | |
352 | |
353 Notes | |
354 ----- | |
355 Edge weight attributes must be numerical. | |
356 Distances are calculated as sums of weighted edges traversed. | |
357 | |
358 The weight function can be used to hide edges by returning None. | |
359 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None`` | |
360 will find the shortest red path. | |
361 | |
362 See Also | |
363 -------- | |
364 single_source_dijkstra(), single_source_bellman_ford_path_length() | |
365 | |
366 """ | |
367 return multi_source_dijkstra_path_length(G, {source}, cutoff=cutoff, weight=weight) | |
368 | |
369 | |
370 def single_source_dijkstra(G, source, target=None, cutoff=None, weight="weight"): | |
371 """Find shortest weighted paths and lengths from a source node. | |
372 | |
373 Compute the shortest path length between source and all other | |
374 reachable nodes for a weighted graph. | |
375 | |
376 Uses Dijkstra's algorithm to compute shortest paths and lengths | |
377 between a source and all other reachable nodes in a weighted graph. | |
378 | |
379 Parameters | |
380 ---------- | |
381 G : NetworkX graph | |
382 | |
383 source : node label | |
384 Starting node for path | |
385 | |
386 target : node label, optional | |
387 Ending node for path | |
388 | |
389 cutoff : integer or float, optional | |
390 Depth to stop the search. Only return paths with length <= cutoff. | |
391 | |
392 weight : string or function | |
393 If this is a string, then edge weights will be accessed via the | |
394 edge attribute with this key (that is, the weight of the edge | |
395 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no | |
396 such edge attribute exists, the weight of the edge is assumed to | |
397 be one. | |
398 | |
399 If this is a function, the weight of an edge is the value | |
400 returned by the function. The function must accept exactly three | |
401 positional arguments: the two endpoints of an edge and the | |
402 dictionary of edge attributes for that edge. The function must | |
403 return a number. | |
404 | |
405 Returns | |
406 ------- | |
407 distance, path : pair of dictionaries, or numeric and list. | |
408 If target is None, paths and lengths to all nodes are computed. | |
409 The return value is a tuple of two dictionaries keyed by target nodes. | |
410 The first dictionary stores distance to each target node. | |
411 The second stores the path to each target node. | |
412 If target is not None, returns a tuple (distance, path), where | |
413 distance is the distance from source to target and path is a list | |
414 representing the path from source to target. | |
415 | |
416 Raises | |
417 ------ | |
418 NodeNotFound | |
419 If `source` is not in `G`. | |
420 | |
421 Examples | |
422 -------- | |
423 >>> G = nx.path_graph(5) | |
424 >>> length, path = nx.single_source_dijkstra(G, 0) | |
425 >>> print(length[4]) | |
426 4 | |
427 >>> for node in [0, 1, 2, 3, 4]: | |
428 ... print(f"{node}: {length[node]}") | |
429 0: 0 | |
430 1: 1 | |
431 2: 2 | |
432 3: 3 | |
433 4: 4 | |
434 >>> path[4] | |
435 [0, 1, 2, 3, 4] | |
436 >>> length, path = nx.single_source_dijkstra(G, 0, 1) | |
437 >>> length | |
438 1 | |
439 >>> path | |
440 [0, 1] | |
441 | |
442 Notes | |
443 ----- | |
444 Edge weight attributes must be numerical. | |
445 Distances are calculated as sums of weighted edges traversed. | |
446 | |
447 The weight function can be used to hide edges by returning None. | |
448 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None`` | |
449 will find the shortest red path. | |
450 | |
451 Based on the Python cookbook recipe (119466) at | |
452 http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466 | |
453 | |
454 This algorithm is not guaranteed to work if edge weights | |
455 are negative or are floating point numbers | |
456 (overflows and roundoff errors can cause problems). | |
457 | |
458 See Also | |
459 -------- | |
460 single_source_dijkstra_path() | |
461 single_source_dijkstra_path_length() | |
462 single_source_bellman_ford() | |
463 """ | |
464 return multi_source_dijkstra( | |
465 G, {source}, cutoff=cutoff, target=target, weight=weight | |
466 ) | |
467 | |
468 | |
469 def multi_source_dijkstra_path(G, sources, cutoff=None, weight="weight"): | |
470 """Find shortest weighted paths in G from a given set of source | |
471 nodes. | |
472 | |
473 Compute shortest path between any of the source nodes and all other | |
474 reachable nodes for a weighted graph. | |
475 | |
476 Parameters | |
477 ---------- | |
478 G : NetworkX graph | |
479 | |
480 sources : non-empty set of nodes | |
481 Starting nodes for paths. If this is just a set containing a | |
482 single node, then all paths computed by this function will start | |
483 from that node. If there are two or more nodes in the set, the | |
484 computed paths may begin from any one of the start nodes. | |
485 | |
486 cutoff : integer or float, optional | |
487 Depth to stop the search. Only return paths with length <= cutoff. | |
488 | |
489 weight : string or function | |
490 If this is a string, then edge weights will be accessed via the | |
491 edge attribute with this key (that is, the weight of the edge | |
492 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no | |
493 such edge attribute exists, the weight of the edge is assumed to | |
494 be one. | |
495 | |
496 If this is a function, the weight of an edge is the value | |
497 returned by the function. The function must accept exactly three | |
498 positional arguments: the two endpoints of an edge and the | |
499 dictionary of edge attributes for that edge. The function must | |
500 return a number. | |
501 | |
502 Returns | |
503 ------- | |
504 paths : dictionary | |
505 Dictionary of shortest paths keyed by target. | |
506 | |
507 Examples | |
508 -------- | |
509 >>> G = nx.path_graph(5) | |
510 >>> path = nx.multi_source_dijkstra_path(G, {0, 4}) | |
511 >>> path[1] | |
512 [0, 1] | |
513 >>> path[3] | |
514 [4, 3] | |
515 | |
516 Notes | |
517 ----- | |
518 Edge weight attributes must be numerical. | |
519 Distances are calculated as sums of weighted edges traversed. | |
520 | |
521 The weight function can be used to hide edges by returning None. | |
522 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None`` | |
523 will find the shortest red path. | |
524 | |
525 Raises | |
526 ------ | |
527 ValueError | |
528 If `sources` is empty. | |
529 NodeNotFound | |
530 If any of `sources` is not in `G`. | |
531 | |
532 See Also | |
533 -------- | |
534 multi_source_dijkstra(), multi_source_bellman_ford() | |
535 | |
536 """ | |
537 length, path = multi_source_dijkstra(G, sources, cutoff=cutoff, weight=weight) | |
538 return path | |
539 | |
540 | |
541 def multi_source_dijkstra_path_length(G, sources, cutoff=None, weight="weight"): | |
542 """Find shortest weighted path lengths in G from a given set of | |
543 source nodes. | |
544 | |
545 Compute the shortest path length between any of the source nodes and | |
546 all other reachable nodes for a weighted graph. | |
547 | |
548 Parameters | |
549 ---------- | |
550 G : NetworkX graph | |
551 | |
552 sources : non-empty set of nodes | |
553 Starting nodes for paths. If this is just a set containing a | |
554 single node, then all paths computed by this function will start | |
555 from that node. If there are two or more nodes in the set, the | |
556 computed paths may begin from any one of the start nodes. | |
557 | |
558 cutoff : integer or float, optional | |
559 Depth to stop the search. Only return paths with length <= cutoff. | |
560 | |
561 weight : string or function | |
562 If this is a string, then edge weights will be accessed via the | |
563 edge attribute with this key (that is, the weight of the edge | |
564 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no | |
565 such edge attribute exists, the weight of the edge is assumed to | |
566 be one. | |
567 | |
568 If this is a function, the weight of an edge is the value | |
569 returned by the function. The function must accept exactly three | |
570 positional arguments: the two endpoints of an edge and the | |
571 dictionary of edge attributes for that edge. The function must | |
572 return a number. | |
573 | |
574 Returns | |
575 ------- | |
576 length : dict | |
577 Dict keyed by node to shortest path length to nearest source. | |
578 | |
579 Examples | |
580 -------- | |
581 >>> G = nx.path_graph(5) | |
582 >>> length = nx.multi_source_dijkstra_path_length(G, {0, 4}) | |
583 >>> for node in [0, 1, 2, 3, 4]: | |
584 ... print(f"{node}: {length[node]}") | |
585 0: 0 | |
586 1: 1 | |
587 2: 2 | |
588 3: 1 | |
589 4: 0 | |
590 | |
591 Notes | |
592 ----- | |
593 Edge weight attributes must be numerical. | |
594 Distances are calculated as sums of weighted edges traversed. | |
595 | |
596 The weight function can be used to hide edges by returning None. | |
597 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None`` | |
598 will find the shortest red path. | |
599 | |
600 Raises | |
601 ------ | |
602 ValueError | |
603 If `sources` is empty. | |
604 NodeNotFound | |
605 If any of `sources` is not in `G`. | |
606 | |
607 See Also | |
608 -------- | |
609 multi_source_dijkstra() | |
610 | |
611 """ | |
612 if not sources: | |
613 raise ValueError("sources must not be empty") | |
614 weight = _weight_function(G, weight) | |
615 return _dijkstra_multisource(G, sources, weight, cutoff=cutoff) | |
616 | |
617 | |
618 def multi_source_dijkstra(G, sources, target=None, cutoff=None, weight="weight"): | |
619 """Find shortest weighted paths and lengths from a given set of | |
620 source nodes. | |
621 | |
622 Uses Dijkstra's algorithm to compute the shortest paths and lengths | |
623 between one of the source nodes and the given `target`, or all other | |
624 reachable nodes if not specified, for a weighted graph. | |
625 | |
626 Parameters | |
627 ---------- | |
628 G : NetworkX graph | |
629 | |
630 sources : non-empty set of nodes | |
631 Starting nodes for paths. If this is just a set containing a | |
632 single node, then all paths computed by this function will start | |
633 from that node. If there are two or more nodes in the set, the | |
634 computed paths may begin from any one of the start nodes. | |
635 | |
636 target : node label, optional | |
637 Ending node for path | |
638 | |
639 cutoff : integer or float, optional | |
640 Depth to stop the search. Only return paths with length <= cutoff. | |
641 | |
642 weight : string or function | |
643 If this is a string, then edge weights will be accessed via the | |
644 edge attribute with this key (that is, the weight of the edge | |
645 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no | |
646 such edge attribute exists, the weight of the edge is assumed to | |
647 be one. | |
648 | |
649 If this is a function, the weight of an edge is the value | |
650 returned by the function. The function must accept exactly three | |
651 positional arguments: the two endpoints of an edge and the | |
652 dictionary of edge attributes for that edge. The function must | |
653 return a number. | |
654 | |
655 Returns | |
656 ------- | |
657 distance, path : pair of dictionaries, or numeric and list | |
658 If target is None, returns a tuple of two dictionaries keyed by node. | |
659 The first dictionary stores distance from one of the source nodes. | |
660 The second stores the path from one of the sources to that node. | |
661 If target is not None, returns a tuple of (distance, path) where | |
662 distance is the distance from source to target and path is a list | |
663 representing the path from source to target. | |
664 | |
665 Examples | |
666 -------- | |
667 >>> G = nx.path_graph(5) | |
668 >>> length, path = nx.multi_source_dijkstra(G, {0, 4}) | |
669 >>> for node in [0, 1, 2, 3, 4]: | |
670 ... print(f"{node}: {length[node]}") | |
671 0: 0 | |
672 1: 1 | |
673 2: 2 | |
674 3: 1 | |
675 4: 0 | |
676 >>> path[1] | |
677 [0, 1] | |
678 >>> path[3] | |
679 [4, 3] | |
680 | |
681 >>> length, path = nx.multi_source_dijkstra(G, {0, 4}, 1) | |
682 >>> length | |
683 1 | |
684 >>> path | |
685 [0, 1] | |
686 | |
687 Notes | |
688 ----- | |
689 Edge weight attributes must be numerical. | |
690 Distances are calculated as sums of weighted edges traversed. | |
691 | |
692 The weight function can be used to hide edges by returning None. | |
693 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None`` | |
694 will find the shortest red path. | |
695 | |
696 Based on the Python cookbook recipe (119466) at | |
697 http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466 | |
698 | |
699 This algorithm is not guaranteed to work if edge weights | |
700 are negative or are floating point numbers | |
701 (overflows and roundoff errors can cause problems). | |
702 | |
703 Raises | |
704 ------ | |
705 ValueError | |
706 If `sources` is empty. | |
707 NodeNotFound | |
708 If any of `sources` is not in `G`. | |
709 | |
710 See Also | |
711 -------- | |
712 multi_source_dijkstra_path() | |
713 multi_source_dijkstra_path_length() | |
714 | |
715 """ | |
716 if not sources: | |
717 raise ValueError("sources must not be empty") | |
718 if target in sources: | |
719 return (0, [target]) | |
720 weight = _weight_function(G, weight) | |
721 paths = {source: [source] for source in sources} # dictionary of paths | |
722 dist = _dijkstra_multisource( | |
723 G, sources, weight, paths=paths, cutoff=cutoff, target=target | |
724 ) | |
725 if target is None: | |
726 return (dist, paths) | |
727 try: | |
728 return (dist[target], paths[target]) | |
729 except KeyError as e: | |
730 raise nx.NetworkXNoPath(f"No path to {target}.") from e | |
731 | |
732 | |
733 def _dijkstra(G, source, weight, pred=None, paths=None, cutoff=None, target=None): | |
734 """Uses Dijkstra's algorithm to find shortest weighted paths from a | |
735 single source. | |
736 | |
737 This is a convenience function for :func:`_dijkstra_multisource` | |
738 with all the arguments the same, except the keyword argument | |
739 `sources` set to ``[source]``. | |
740 | |
741 """ | |
742 return _dijkstra_multisource( | |
743 G, [source], weight, pred=pred, paths=paths, cutoff=cutoff, target=target | |
744 ) | |
745 | |
746 | |
747 def _dijkstra_multisource( | |
748 G, sources, weight, pred=None, paths=None, cutoff=None, target=None | |
749 ): | |
750 """Uses Dijkstra's algorithm to find shortest weighted paths | |
751 | |
752 Parameters | |
753 ---------- | |
754 G : NetworkX graph | |
755 | |
756 sources : non-empty iterable of nodes | |
757 Starting nodes for paths. If this is just an iterable containing | |
758 a single node, then all paths computed by this function will | |
759 start from that node. If there are two or more nodes in this | |
760 iterable, the computed paths may begin from any one of the start | |
761 nodes. | |
762 | |
763 weight: function | |
764 Function with (u, v, data) input that returns that edges weight | |
765 | |
766 pred: dict of lists, optional(default=None) | |
767 dict to store a list of predecessors keyed by that node | |
768 If None, predecessors are not stored. | |
769 | |
770 paths: dict, optional (default=None) | |
771 dict to store the path list from source to each node, keyed by node. | |
772 If None, paths are not stored. | |
773 | |
774 target : node label, optional | |
775 Ending node for path. Search is halted when target is found. | |
776 | |
777 cutoff : integer or float, optional | |
778 Depth to stop the search. Only return paths with length <= cutoff. | |
779 | |
780 Returns | |
781 ------- | |
782 distance : dictionary | |
783 A mapping from node to shortest distance to that node from one | |
784 of the source nodes. | |
785 | |
786 Raises | |
787 ------ | |
788 NodeNotFound | |
789 If any of `sources` is not in `G`. | |
790 | |
791 Notes | |
792 ----- | |
793 The optional predecessor and path dictionaries can be accessed by | |
794 the caller through the original pred and paths objects passed | |
795 as arguments. No need to explicitly return pred or paths. | |
796 | |
797 """ | |
798 G_succ = G._succ if G.is_directed() else G._adj | |
799 | |
800 push = heappush | |
801 pop = heappop | |
802 dist = {} # dictionary of final distances | |
803 seen = {} | |
804 # fringe is heapq with 3-tuples (distance,c,node) | |
805 # use the count c to avoid comparing nodes (may not be able to) | |
806 c = count() | |
807 fringe = [] | |
808 for source in sources: | |
809 if source not in G: | |
810 raise nx.NodeNotFound(f"Source {source} not in G") | |
811 seen[source] = 0 | |
812 push(fringe, (0, next(c), source)) | |
813 while fringe: | |
814 (d, _, v) = pop(fringe) | |
815 if v in dist: | |
816 continue # already searched this node. | |
817 dist[v] = d | |
818 if v == target: | |
819 break | |
820 for u, e in G_succ[v].items(): | |
821 cost = weight(v, u, e) | |
822 if cost is None: | |
823 continue | |
824 vu_dist = dist[v] + cost | |
825 if cutoff is not None: | |
826 if vu_dist > cutoff: | |
827 continue | |
828 if u in dist: | |
829 u_dist = dist[u] | |
830 if vu_dist < u_dist: | |
831 raise ValueError("Contradictory paths found:", "negative weights?") | |
832 elif pred is not None and vu_dist == u_dist: | |
833 pred[u].append(v) | |
834 elif u not in seen or vu_dist < seen[u]: | |
835 seen[u] = vu_dist | |
836 push(fringe, (vu_dist, next(c), u)) | |
837 if paths is not None: | |
838 paths[u] = paths[v] + [u] | |
839 if pred is not None: | |
840 pred[u] = [v] | |
841 elif vu_dist == seen[u]: | |
842 if pred is not None: | |
843 pred[u].append(v) | |
844 | |
845 # The optional predecessor and path dictionaries can be accessed | |
846 # by the caller via the pred and paths objects passed as arguments. | |
847 return dist | |
848 | |
849 | |
850 def dijkstra_predecessor_and_distance(G, source, cutoff=None, weight="weight"): | |
851 """Compute weighted shortest path length and predecessors. | |
852 | |
853 Uses Dijkstra's Method to obtain the shortest weighted paths | |
854 and return dictionaries of predecessors for each node and | |
855 distance for each node from the `source`. | |
856 | |
857 Parameters | |
858 ---------- | |
859 G : NetworkX graph | |
860 | |
861 source : node label | |
862 Starting node for path | |
863 | |
864 cutoff : integer or float, optional | |
865 Depth to stop the search. Only return paths with length <= cutoff. | |
866 | |
867 weight : string or function | |
868 If this is a string, then edge weights will be accessed via the | |
869 edge attribute with this key (that is, the weight of the edge | |
870 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no | |
871 such edge attribute exists, the weight of the edge is assumed to | |
872 be one. | |
873 | |
874 If this is a function, the weight of an edge is the value | |
875 returned by the function. The function must accept exactly three | |
876 positional arguments: the two endpoints of an edge and the | |
877 dictionary of edge attributes for that edge. The function must | |
878 return a number. | |
879 | |
880 Returns | |
881 ------- | |
882 pred, distance : dictionaries | |
883 Returns two dictionaries representing a list of predecessors | |
884 of a node and the distance to each node. | |
885 Warning: If target is specified, the dicts are incomplete as they | |
886 only contain information for the nodes along a path to target. | |
887 | |
888 Raises | |
889 ------ | |
890 NodeNotFound | |
891 If `source` is not in `G`. | |
892 | |
893 Notes | |
894 ----- | |
895 Edge weight attributes must be numerical. | |
896 Distances are calculated as sums of weighted edges traversed. | |
897 | |
898 The list of predecessors contains more than one element only when | |
899 there are more than one shortest paths to the key node. | |
900 | |
901 Examples | |
902 -------- | |
903 >>> G = nx.path_graph(5, create_using=nx.DiGraph()) | |
904 >>> pred, dist = nx.dijkstra_predecessor_and_distance(G, 0) | |
905 >>> sorted(pred.items()) | |
906 [(0, []), (1, [0]), (2, [1]), (3, [2]), (4, [3])] | |
907 >>> sorted(dist.items()) | |
908 [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)] | |
909 | |
910 >>> pred, dist = nx.dijkstra_predecessor_and_distance(G, 0, 1) | |
911 >>> sorted(pred.items()) | |
912 [(0, []), (1, [0])] | |
913 >>> sorted(dist.items()) | |
914 [(0, 0), (1, 1)] | |
915 """ | |
916 | |
917 weight = _weight_function(G, weight) | |
918 pred = {source: []} # dictionary of predecessors | |
919 return (pred, _dijkstra(G, source, weight, pred=pred, cutoff=cutoff)) | |
920 | |
921 | |
922 def all_pairs_dijkstra(G, cutoff=None, weight="weight"): | |
923 """Find shortest weighted paths and lengths between all nodes. | |
924 | |
925 Parameters | |
926 ---------- | |
927 G : NetworkX graph | |
928 | |
929 cutoff : integer or float, optional | |
930 Depth to stop the search. Only return paths with length <= cutoff. | |
931 | |
932 weight : string or function | |
933 If this is a string, then edge weights will be accessed via the | |
934 edge attribute with this key (that is, the weight of the edge | |
935 joining `u` to `v` will be ``G.edge[u][v][weight]``). If no | |
936 such edge attribute exists, the weight of the edge is assumed to | |
937 be one. | |
938 | |
939 If this is a function, the weight of an edge is the value | |
940 returned by the function. The function must accept exactly three | |
941 positional arguments: the two endpoints of an edge and the | |
942 dictionary of edge attributes for that edge. The function must | |
943 return a number. | |
944 | |
945 Yields | |
946 ------ | |
947 (node, (distance, path)) : (node obj, (dict, dict)) | |
948 Each source node has two associated dicts. The first holds distance | |
949 keyed by target and the second holds paths keyed by target. | |
950 (See single_source_dijkstra for the source/target node terminology.) | |
951 If desired you can apply `dict()` to this function to create a dict | |
952 keyed by source node to the two dicts. | |
953 | |
954 Examples | |
955 -------- | |
956 >>> G = nx.path_graph(5) | |
957 >>> len_path = dict(nx.all_pairs_dijkstra(G)) | |
958 >>> print(len_path[3][0][1]) | |
959 2 | |
960 >>> for node in [0, 1, 2, 3, 4]: | |
961 ... print(f"3 - {node}: {len_path[3][0][node]}") | |
962 3 - 0: 3 | |
963 3 - 1: 2 | |
964 3 - 2: 1 | |
965 3 - 3: 0 | |
966 3 - 4: 1 | |
967 >>> len_path[3][1][1] | |
968 [3, 2, 1] | |
969 >>> for n, (dist, path) in nx.all_pairs_dijkstra(G): | |
970 ... print(path[1]) | |
971 [0, 1] | |
972 [1] | |
973 [2, 1] | |
974 [3, 2, 1] | |
975 [4, 3, 2, 1] | |
976 | |
977 Notes | |
978 ----- | |
979 Edge weight attributes must be numerical. | |
980 Distances are calculated as sums of weighted edges traversed. | |
981 | |
982 The yielded dicts only have keys for reachable nodes. | |
983 """ | |
984 for n in G: | |
985 dist, path = single_source_dijkstra(G, n, cutoff=cutoff, weight=weight) | |
986 yield (n, (dist, path)) | |
987 | |
988 | |
989 def all_pairs_dijkstra_path_length(G, cutoff=None, weight="weight"): | |
990 """Compute shortest path lengths between all nodes in a weighted graph. | |
991 | |
992 Parameters | |
993 ---------- | |
994 G : NetworkX graph | |
995 | |
996 cutoff : integer or float, optional | |
997 Depth to stop the search. Only return paths with length <= cutoff. | |
998 | |
999 weight : string or function | |
1000 If this is a string, then edge weights will be accessed via the | |
1001 edge attribute with this key (that is, the weight of the edge | |
1002 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no | |
1003 such edge attribute exists, the weight of the edge is assumed to | |
1004 be one. | |
1005 | |
1006 If this is a function, the weight of an edge is the value | |
1007 returned by the function. The function must accept exactly three | |
1008 positional arguments: the two endpoints of an edge and the | |
1009 dictionary of edge attributes for that edge. The function must | |
1010 return a number. | |
1011 | |
1012 Returns | |
1013 ------- | |
1014 distance : iterator | |
1015 (source, dictionary) iterator with dictionary keyed by target and | |
1016 shortest path length as the key value. | |
1017 | |
1018 Examples | |
1019 -------- | |
1020 >>> G = nx.path_graph(5) | |
1021 >>> length = dict(nx.all_pairs_dijkstra_path_length(G)) | |
1022 >>> for node in [0, 1, 2, 3, 4]: | |
1023 ... print(f"1 - {node}: {length[1][node]}") | |
1024 1 - 0: 1 | |
1025 1 - 1: 0 | |
1026 1 - 2: 1 | |
1027 1 - 3: 2 | |
1028 1 - 4: 3 | |
1029 >>> length[3][2] | |
1030 1 | |
1031 >>> length[2][2] | |
1032 0 | |
1033 | |
1034 Notes | |
1035 ----- | |
1036 Edge weight attributes must be numerical. | |
1037 Distances are calculated as sums of weighted edges traversed. | |
1038 | |
1039 The dictionary returned only has keys for reachable node pairs. | |
1040 """ | |
1041 length = single_source_dijkstra_path_length | |
1042 for n in G: | |
1043 yield (n, length(G, n, cutoff=cutoff, weight=weight)) | |
1044 | |
1045 | |
1046 def all_pairs_dijkstra_path(G, cutoff=None, weight="weight"): | |
1047 """Compute shortest paths between all nodes in a weighted graph. | |
1048 | |
1049 Parameters | |
1050 ---------- | |
1051 G : NetworkX graph | |
1052 | |
1053 cutoff : integer or float, optional | |
1054 Depth to stop the search. Only return paths with length <= cutoff. | |
1055 | |
1056 weight : string or function | |
1057 If this is a string, then edge weights will be accessed via the | |
1058 edge attribute with this key (that is, the weight of the edge | |
1059 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no | |
1060 such edge attribute exists, the weight of the edge is assumed to | |
1061 be one. | |
1062 | |
1063 If this is a function, the weight of an edge is the value | |
1064 returned by the function. The function must accept exactly three | |
1065 positional arguments: the two endpoints of an edge and the | |
1066 dictionary of edge attributes for that edge. The function must | |
1067 return a number. | |
1068 | |
1069 Returns | |
1070 ------- | |
1071 distance : dictionary | |
1072 Dictionary, keyed by source and target, of shortest paths. | |
1073 | |
1074 Examples | |
1075 -------- | |
1076 >>> G = nx.path_graph(5) | |
1077 >>> path = dict(nx.all_pairs_dijkstra_path(G)) | |
1078 >>> print(path[0][4]) | |
1079 [0, 1, 2, 3, 4] | |
1080 | |
1081 Notes | |
1082 ----- | |
1083 Edge weight attributes must be numerical. | |
1084 Distances are calculated as sums of weighted edges traversed. | |
1085 | |
1086 See Also | |
1087 -------- | |
1088 floyd_warshall(), all_pairs_bellman_ford_path() | |
1089 | |
1090 """ | |
1091 path = single_source_dijkstra_path | |
1092 # TODO This can be trivially parallelized. | |
1093 for n in G: | |
1094 yield (n, path(G, n, cutoff=cutoff, weight=weight)) | |
1095 | |
1096 | |
1097 def bellman_ford_predecessor_and_distance( | |
1098 G, source, target=None, weight="weight", heuristic=False | |
1099 ): | |
1100 """Compute shortest path lengths and predecessors on shortest paths | |
1101 in weighted graphs. | |
1102 | |
1103 The algorithm has a running time of $O(mn)$ where $n$ is the number of | |
1104 nodes and $m$ is the number of edges. It is slower than Dijkstra but | |
1105 can handle negative edge weights. | |
1106 | |
1107 Parameters | |
1108 ---------- | |
1109 G : NetworkX graph | |
1110 The algorithm works for all types of graphs, including directed | |
1111 graphs and multigraphs. | |
1112 | |
1113 source: node label | |
1114 Starting node for path | |
1115 | |
1116 weight : string or function | |
1117 If this is a string, then edge weights will be accessed via the | |
1118 edge attribute with this key (that is, the weight of the edge | |
1119 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no | |
1120 such edge attribute exists, the weight of the edge is assumed to | |
1121 be one. | |
1122 | |
1123 If this is a function, the weight of an edge is the value | |
1124 returned by the function. The function must accept exactly three | |
1125 positional arguments: the two endpoints of an edge and the | |
1126 dictionary of edge attributes for that edge. The function must | |
1127 return a number. | |
1128 | |
1129 heuristic : bool | |
1130 Determines whether to use a heuristic to early detect negative | |
1131 cycles at a hopefully negligible cost. | |
1132 | |
1133 Returns | |
1134 ------- | |
1135 pred, dist : dictionaries | |
1136 Returns two dictionaries keyed by node to predecessor in the | |
1137 path and to the distance from the source respectively. | |
1138 | |
1139 Raises | |
1140 ------ | |
1141 NodeNotFound | |
1142 If `source` is not in `G`. | |
1143 | |
1144 NetworkXUnbounded | |
1145 If the (di)graph contains a negative cost (di)cycle, the | |
1146 algorithm raises an exception to indicate the presence of the | |
1147 negative cost (di)cycle. Note: any negative weight edge in an | |
1148 undirected graph is a negative cost cycle. | |
1149 | |
1150 Examples | |
1151 -------- | |
1152 >>> G = nx.path_graph(5, create_using=nx.DiGraph()) | |
1153 >>> pred, dist = nx.bellman_ford_predecessor_and_distance(G, 0) | |
1154 >>> sorted(pred.items()) | |
1155 [(0, []), (1, [0]), (2, [1]), (3, [2]), (4, [3])] | |
1156 >>> sorted(dist.items()) | |
1157 [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)] | |
1158 | |
1159 >>> pred, dist = nx.bellman_ford_predecessor_and_distance(G, 0, 1) | |
1160 >>> sorted(pred.items()) | |
1161 [(0, []), (1, [0]), (2, [1]), (3, [2]), (4, [3])] | |
1162 >>> sorted(dist.items()) | |
1163 [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)] | |
1164 | |
1165 >>> G = nx.cycle_graph(5, create_using=nx.DiGraph()) | |
1166 >>> G[1][2]["weight"] = -7 | |
1167 >>> nx.bellman_ford_predecessor_and_distance(G, 0) | |
1168 Traceback (most recent call last): | |
1169 ... | |
1170 networkx.exception.NetworkXUnbounded: Negative cost cycle detected. | |
1171 | |
1172 Notes | |
1173 ----- | |
1174 Edge weight attributes must be numerical. | |
1175 Distances are calculated as sums of weighted edges traversed. | |
1176 | |
1177 The dictionaries returned only have keys for nodes reachable from | |
1178 the source. | |
1179 | |
1180 In the case where the (di)graph is not connected, if a component | |
1181 not containing the source contains a negative cost (di)cycle, it | |
1182 will not be detected. | |
1183 | |
1184 In NetworkX v2.1 and prior, the source node had predecessor `[None]`. | |
1185 In NetworkX v2.2 this changed to the source node having predecessor `[]` | |
1186 """ | |
1187 if source not in G: | |
1188 raise nx.NodeNotFound(f"Node {source} is not found in the graph") | |
1189 weight = _weight_function(G, weight) | |
1190 if any(weight(u, v, d) < 0 for u, v, d in nx.selfloop_edges(G, data=True)): | |
1191 raise nx.NetworkXUnbounded("Negative cost cycle detected.") | |
1192 | |
1193 dist = {source: 0} | |
1194 pred = {source: []} | |
1195 | |
1196 if len(G) == 1: | |
1197 return pred, dist | |
1198 | |
1199 weight = _weight_function(G, weight) | |
1200 | |
1201 dist = _bellman_ford( | |
1202 G, [source], weight, pred=pred, dist=dist, target=target, heuristic=heuristic | |
1203 ) | |
1204 return (pred, dist) | |
1205 | |
1206 | |
1207 def _bellman_ford( | |
1208 G, source, weight, pred=None, paths=None, dist=None, target=None, heuristic=True | |
1209 ): | |
1210 """Relaxation loop for Bellman–Ford algorithm. | |
1211 | |
1212 This is an implementation of the SPFA variant. | |
1213 See https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm | |
1214 | |
1215 Parameters | |
1216 ---------- | |
1217 G : NetworkX graph | |
1218 | |
1219 source: list | |
1220 List of source nodes. The shortest path from any of the source | |
1221 nodes will be found if multiple sources are provided. | |
1222 | |
1223 weight : function | |
1224 The weight of an edge is the value returned by the function. The | |
1225 function must accept exactly three positional arguments: the two | |
1226 endpoints of an edge and the dictionary of edge attributes for | |
1227 that edge. The function must return a number. | |
1228 | |
1229 pred: dict of lists, optional (default=None) | |
1230 dict to store a list of predecessors keyed by that node | |
1231 If None, predecessors are not stored | |
1232 | |
1233 paths: dict, optional (default=None) | |
1234 dict to store the path list from source to each node, keyed by node | |
1235 If None, paths are not stored | |
1236 | |
1237 dist: dict, optional (default=None) | |
1238 dict to store distance from source to the keyed node | |
1239 If None, returned dist dict contents default to 0 for every node in the | |
1240 source list | |
1241 | |
1242 target: node label, optional | |
1243 Ending node for path. Path lengths to other destinations may (and | |
1244 probably will) be incorrect. | |
1245 | |
1246 heuristic : bool | |
1247 Determines whether to use a heuristic to early detect negative | |
1248 cycles at a hopefully negligible cost. | |
1249 | |
1250 Returns | |
1251 ------- | |
1252 Returns a dict keyed by node to the distance from the source. | |
1253 Dicts for paths and pred are in the mutated input dicts by those names. | |
1254 | |
1255 Raises | |
1256 ------ | |
1257 NodeNotFound | |
1258 If any of `source` is not in `G`. | |
1259 | |
1260 NetworkXUnbounded | |
1261 If the (di)graph contains a negative cost (di)cycle, the | |
1262 algorithm raises an exception to indicate the presence of the | |
1263 negative cost (di)cycle. Note: any negative weight edge in an | |
1264 undirected graph is a negative cost cycle | |
1265 """ | |
1266 for s in source: | |
1267 if s not in G: | |
1268 raise nx.NodeNotFound(f"Source {s} not in G") | |
1269 | |
1270 if pred is None: | |
1271 pred = {v: [] for v in source} | |
1272 | |
1273 if dist is None: | |
1274 dist = {v: 0 for v in source} | |
1275 | |
1276 # Heuristic Storage setup. Note: use None because nodes cannot be None | |
1277 nonexistent_edge = (None, None) | |
1278 pred_edge = {v: None for v in source} | |
1279 recent_update = {v: nonexistent_edge for v in source} | |
1280 | |
1281 G_succ = G.succ if G.is_directed() else G.adj | |
1282 inf = float("inf") | |
1283 n = len(G) | |
1284 | |
1285 count = {} | |
1286 q = deque(source) | |
1287 in_q = set(source) | |
1288 while q: | |
1289 u = q.popleft() | |
1290 in_q.remove(u) | |
1291 | |
1292 # Skip relaxations if any of the predecessors of u is in the queue. | |
1293 if all(pred_u not in in_q for pred_u in pred[u]): | |
1294 dist_u = dist[u] | |
1295 for v, e in G_succ[u].items(): | |
1296 dist_v = dist_u + weight(u, v, e) | |
1297 | |
1298 if dist_v < dist.get(v, inf): | |
1299 # In this conditional branch we are updating the path with v. | |
1300 # If it happens that some earlier update also added node v | |
1301 # that implies the existence of a negative cycle since | |
1302 # after the update node v would lie on the update path twice. | |
1303 # The update path is stored up to one of the source nodes, | |
1304 # therefore u is always in the dict recent_update | |
1305 if heuristic: | |
1306 if v in recent_update[u]: | |
1307 raise nx.NetworkXUnbounded("Negative cost cycle detected.") | |
1308 # Transfer the recent update info from u to v if the | |
1309 # same source node is the head of the update path. | |
1310 # If the source node is responsible for the cost update, | |
1311 # then clear the history and use it instead. | |
1312 if v in pred_edge and pred_edge[v] == u: | |
1313 recent_update[v] = recent_update[u] | |
1314 else: | |
1315 recent_update[v] = (u, v) | |
1316 | |
1317 if v not in in_q: | |
1318 q.append(v) | |
1319 in_q.add(v) | |
1320 count_v = count.get(v, 0) + 1 | |
1321 if count_v == n: | |
1322 raise nx.NetworkXUnbounded("Negative cost cycle detected.") | |
1323 count[v] = count_v | |
1324 dist[v] = dist_v | |
1325 pred[v] = [u] | |
1326 pred_edge[v] = u | |
1327 | |
1328 elif dist.get(v) is not None and dist_v == dist.get(v): | |
1329 pred[v].append(u) | |
1330 | |
1331 if paths is not None: | |
1332 sources = set(source) | |
1333 dsts = [target] if target is not None else pred | |
1334 for dst in dsts: | |
1335 gen = _build_paths_from_predecessors(sources, dst, pred) | |
1336 paths[dst] = next(gen) | |
1337 | |
1338 return dist | |
1339 | |
1340 | |
1341 def bellman_ford_path(G, source, target, weight="weight"): | |
1342 """Returns the shortest path from source to target in a weighted graph G. | |
1343 | |
1344 Parameters | |
1345 ---------- | |
1346 G : NetworkX graph | |
1347 | |
1348 source : node | |
1349 Starting node | |
1350 | |
1351 target : node | |
1352 Ending node | |
1353 | |
1354 weight: string, optional (default='weight') | |
1355 Edge data key corresponding to the edge weight | |
1356 | |
1357 Returns | |
1358 ------- | |
1359 path : list | |
1360 List of nodes in a shortest path. | |
1361 | |
1362 Raises | |
1363 ------ | |
1364 NodeNotFound | |
1365 If `source` is not in `G`. | |
1366 | |
1367 NetworkXNoPath | |
1368 If no path exists between source and target. | |
1369 | |
1370 Examples | |
1371 -------- | |
1372 >>> G = nx.path_graph(5) | |
1373 >>> print(nx.bellman_ford_path(G, 0, 4)) | |
1374 [0, 1, 2, 3, 4] | |
1375 | |
1376 Notes | |
1377 ----- | |
1378 Edge weight attributes must be numerical. | |
1379 Distances are calculated as sums of weighted edges traversed. | |
1380 | |
1381 See Also | |
1382 -------- | |
1383 dijkstra_path(), bellman_ford_path_length() | |
1384 """ | |
1385 length, path = single_source_bellman_ford(G, source, target=target, weight=weight) | |
1386 return path | |
1387 | |
1388 | |
1389 def bellman_ford_path_length(G, source, target, weight="weight"): | |
1390 """Returns the shortest path length from source to target | |
1391 in a weighted graph. | |
1392 | |
1393 Parameters | |
1394 ---------- | |
1395 G : NetworkX graph | |
1396 | |
1397 source : node label | |
1398 starting node for path | |
1399 | |
1400 target : node label | |
1401 ending node for path | |
1402 | |
1403 weight: string, optional (default='weight') | |
1404 Edge data key corresponding to the edge weight | |
1405 | |
1406 Returns | |
1407 ------- | |
1408 length : number | |
1409 Shortest path length. | |
1410 | |
1411 Raises | |
1412 ------ | |
1413 NodeNotFound | |
1414 If `source` is not in `G`. | |
1415 | |
1416 NetworkXNoPath | |
1417 If no path exists between source and target. | |
1418 | |
1419 Examples | |
1420 -------- | |
1421 >>> G = nx.path_graph(5) | |
1422 >>> print(nx.bellman_ford_path_length(G, 0, 4)) | |
1423 4 | |
1424 | |
1425 Notes | |
1426 ----- | |
1427 Edge weight attributes must be numerical. | |
1428 Distances are calculated as sums of weighted edges traversed. | |
1429 | |
1430 See Also | |
1431 -------- | |
1432 dijkstra_path_length(), bellman_ford_path() | |
1433 """ | |
1434 if source == target: | |
1435 return 0 | |
1436 | |
1437 weight = _weight_function(G, weight) | |
1438 | |
1439 length = _bellman_ford(G, [source], weight, target=target) | |
1440 | |
1441 try: | |
1442 return length[target] | |
1443 except KeyError as e: | |
1444 raise nx.NetworkXNoPath(f"node {target} not reachable from {source}") from e | |
1445 | |
1446 | |
1447 def single_source_bellman_ford_path(G, source, weight="weight"): | |
1448 """Compute shortest path between source and all other reachable | |
1449 nodes for a weighted graph. | |
1450 | |
1451 Parameters | |
1452 ---------- | |
1453 G : NetworkX graph | |
1454 | |
1455 source : node | |
1456 Starting node for path. | |
1457 | |
1458 weight: string, optional (default='weight') | |
1459 Edge data key corresponding to the edge weight | |
1460 | |
1461 Returns | |
1462 ------- | |
1463 paths : dictionary | |
1464 Dictionary of shortest path lengths keyed by target. | |
1465 | |
1466 Raises | |
1467 ------ | |
1468 NodeNotFound | |
1469 If `source` is not in `G`. | |
1470 | |
1471 Examples | |
1472 -------- | |
1473 >>> G = nx.path_graph(5) | |
1474 >>> path = nx.single_source_bellman_ford_path(G, 0) | |
1475 >>> path[4] | |
1476 [0, 1, 2, 3, 4] | |
1477 | |
1478 Notes | |
1479 ----- | |
1480 Edge weight attributes must be numerical. | |
1481 Distances are calculated as sums of weighted edges traversed. | |
1482 | |
1483 See Also | |
1484 -------- | |
1485 single_source_dijkstra(), single_source_bellman_ford() | |
1486 | |
1487 """ | |
1488 (length, path) = single_source_bellman_ford(G, source, weight=weight) | |
1489 return path | |
1490 | |
1491 | |
1492 def single_source_bellman_ford_path_length(G, source, weight="weight"): | |
1493 """Compute the shortest path length between source and all other | |
1494 reachable nodes for a weighted graph. | |
1495 | |
1496 Parameters | |
1497 ---------- | |
1498 G : NetworkX graph | |
1499 | |
1500 source : node label | |
1501 Starting node for path | |
1502 | |
1503 weight: string, optional (default='weight') | |
1504 Edge data key corresponding to the edge weight. | |
1505 | |
1506 Returns | |
1507 ------- | |
1508 length : iterator | |
1509 (target, shortest path length) iterator | |
1510 | |
1511 Raises | |
1512 ------ | |
1513 NodeNotFound | |
1514 If `source` is not in `G`. | |
1515 | |
1516 Examples | |
1517 -------- | |
1518 >>> G = nx.path_graph(5) | |
1519 >>> length = dict(nx.single_source_bellman_ford_path_length(G, 0)) | |
1520 >>> length[4] | |
1521 4 | |
1522 >>> for node in [0, 1, 2, 3, 4]: | |
1523 ... print(f"{node}: {length[node]}") | |
1524 0: 0 | |
1525 1: 1 | |
1526 2: 2 | |
1527 3: 3 | |
1528 4: 4 | |
1529 | |
1530 Notes | |
1531 ----- | |
1532 Edge weight attributes must be numerical. | |
1533 Distances are calculated as sums of weighted edges traversed. | |
1534 | |
1535 See Also | |
1536 -------- | |
1537 single_source_dijkstra(), single_source_bellman_ford() | |
1538 | |
1539 """ | |
1540 weight = _weight_function(G, weight) | |
1541 return _bellman_ford(G, [source], weight) | |
1542 | |
1543 | |
1544 def single_source_bellman_ford(G, source, target=None, weight="weight"): | |
1545 """Compute shortest paths and lengths in a weighted graph G. | |
1546 | |
1547 Uses Bellman-Ford algorithm for shortest paths. | |
1548 | |
1549 Parameters | |
1550 ---------- | |
1551 G : NetworkX graph | |
1552 | |
1553 source : node label | |
1554 Starting node for path | |
1555 | |
1556 target : node label, optional | |
1557 Ending node for path | |
1558 | |
1559 Returns | |
1560 ------- | |
1561 distance, path : pair of dictionaries, or numeric and list | |
1562 If target is None, returns a tuple of two dictionaries keyed by node. | |
1563 The first dictionary stores distance from one of the source nodes. | |
1564 The second stores the path from one of the sources to that node. | |
1565 If target is not None, returns a tuple of (distance, path) where | |
1566 distance is the distance from source to target and path is a list | |
1567 representing the path from source to target. | |
1568 | |
1569 Raises | |
1570 ------ | |
1571 NodeNotFound | |
1572 If `source` is not in `G`. | |
1573 | |
1574 Examples | |
1575 -------- | |
1576 >>> G = nx.path_graph(5) | |
1577 >>> length, path = nx.single_source_bellman_ford(G, 0) | |
1578 >>> print(length[4]) | |
1579 4 | |
1580 >>> for node in [0, 1, 2, 3, 4]: | |
1581 ... print(f"{node}: {length[node]}") | |
1582 0: 0 | |
1583 1: 1 | |
1584 2: 2 | |
1585 3: 3 | |
1586 4: 4 | |
1587 >>> path[4] | |
1588 [0, 1, 2, 3, 4] | |
1589 >>> length, path = nx.single_source_bellman_ford(G, 0, 1) | |
1590 >>> length | |
1591 1 | |
1592 >>> path | |
1593 [0, 1] | |
1594 | |
1595 Notes | |
1596 ----- | |
1597 Edge weight attributes must be numerical. | |
1598 Distances are calculated as sums of weighted edges traversed. | |
1599 | |
1600 See Also | |
1601 -------- | |
1602 single_source_dijkstra() | |
1603 single_source_bellman_ford_path() | |
1604 single_source_bellman_ford_path_length() | |
1605 """ | |
1606 if source == target: | |
1607 return (0, [source]) | |
1608 | |
1609 weight = _weight_function(G, weight) | |
1610 | |
1611 paths = {source: [source]} # dictionary of paths | |
1612 dist = _bellman_ford(G, [source], weight, paths=paths, target=target) | |
1613 if target is None: | |
1614 return (dist, paths) | |
1615 try: | |
1616 return (dist[target], paths[target]) | |
1617 except KeyError as e: | |
1618 msg = f"Node {target} not reachable from {source}" | |
1619 raise nx.NetworkXNoPath(msg) from e | |
1620 | |
1621 | |
1622 def all_pairs_bellman_ford_path_length(G, weight="weight"): | |
1623 """ Compute shortest path lengths between all nodes in a weighted graph. | |
1624 | |
1625 Parameters | |
1626 ---------- | |
1627 G : NetworkX graph | |
1628 | |
1629 weight: string, optional (default='weight') | |
1630 Edge data key corresponding to the edge weight | |
1631 | |
1632 Returns | |
1633 ------- | |
1634 distance : iterator | |
1635 (source, dictionary) iterator with dictionary keyed by target and | |
1636 shortest path length as the key value. | |
1637 | |
1638 Examples | |
1639 -------- | |
1640 >>> G = nx.path_graph(5) | |
1641 >>> length = dict(nx.all_pairs_bellman_ford_path_length(G)) | |
1642 >>> for node in [0, 1, 2, 3, 4]: | |
1643 ... print(f"1 - {node}: {length[1][node]}") | |
1644 1 - 0: 1 | |
1645 1 - 1: 0 | |
1646 1 - 2: 1 | |
1647 1 - 3: 2 | |
1648 1 - 4: 3 | |
1649 >>> length[3][2] | |
1650 1 | |
1651 >>> length[2][2] | |
1652 0 | |
1653 | |
1654 Notes | |
1655 ----- | |
1656 Edge weight attributes must be numerical. | |
1657 Distances are calculated as sums of weighted edges traversed. | |
1658 | |
1659 The dictionary returned only has keys for reachable node pairs. | |
1660 """ | |
1661 length = single_source_bellman_ford_path_length | |
1662 for n in G: | |
1663 yield (n, dict(length(G, n, weight=weight))) | |
1664 | |
1665 | |
1666 def all_pairs_bellman_ford_path(G, weight="weight"): | |
1667 """ Compute shortest paths between all nodes in a weighted graph. | |
1668 | |
1669 Parameters | |
1670 ---------- | |
1671 G : NetworkX graph | |
1672 | |
1673 weight: string, optional (default='weight') | |
1674 Edge data key corresponding to the edge weight | |
1675 | |
1676 Returns | |
1677 ------- | |
1678 distance : dictionary | |
1679 Dictionary, keyed by source and target, of shortest paths. | |
1680 | |
1681 Examples | |
1682 -------- | |
1683 >>> G = nx.path_graph(5) | |
1684 >>> path = dict(nx.all_pairs_bellman_ford_path(G)) | |
1685 >>> print(path[0][4]) | |
1686 [0, 1, 2, 3, 4] | |
1687 | |
1688 Notes | |
1689 ----- | |
1690 Edge weight attributes must be numerical. | |
1691 Distances are calculated as sums of weighted edges traversed. | |
1692 | |
1693 See Also | |
1694 -------- | |
1695 floyd_warshall(), all_pairs_dijkstra_path() | |
1696 | |
1697 """ | |
1698 path = single_source_bellman_ford_path | |
1699 # TODO This can be trivially parallelized. | |
1700 for n in G: | |
1701 yield (n, path(G, n, weight=weight)) | |
1702 | |
1703 | |
1704 def goldberg_radzik(G, source, weight="weight"): | |
1705 """Compute shortest path lengths and predecessors on shortest paths | |
1706 in weighted graphs. | |
1707 | |
1708 The algorithm has a running time of $O(mn)$ where $n$ is the number of | |
1709 nodes and $m$ is the number of edges. It is slower than Dijkstra but | |
1710 can handle negative edge weights. | |
1711 | |
1712 Parameters | |
1713 ---------- | |
1714 G : NetworkX graph | |
1715 The algorithm works for all types of graphs, including directed | |
1716 graphs and multigraphs. | |
1717 | |
1718 source: node label | |
1719 Starting node for path | |
1720 | |
1721 weight : string or function | |
1722 If this is a string, then edge weights will be accessed via the | |
1723 edge attribute with this key (that is, the weight of the edge | |
1724 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no | |
1725 such edge attribute exists, the weight of the edge is assumed to | |
1726 be one. | |
1727 | |
1728 If this is a function, the weight of an edge is the value | |
1729 returned by the function. The function must accept exactly three | |
1730 positional arguments: the two endpoints of an edge and the | |
1731 dictionary of edge attributes for that edge. The function must | |
1732 return a number. | |
1733 | |
1734 Returns | |
1735 ------- | |
1736 pred, dist : dictionaries | |
1737 Returns two dictionaries keyed by node to predecessor in the | |
1738 path and to the distance from the source respectively. | |
1739 | |
1740 Raises | |
1741 ------ | |
1742 NodeNotFound | |
1743 If `source` is not in `G`. | |
1744 | |
1745 NetworkXUnbounded | |
1746 If the (di)graph contains a negative cost (di)cycle, the | |
1747 algorithm raises an exception to indicate the presence of the | |
1748 negative cost (di)cycle. Note: any negative weight edge in an | |
1749 undirected graph is a negative cost cycle. | |
1750 | |
1751 Examples | |
1752 -------- | |
1753 >>> G = nx.path_graph(5, create_using=nx.DiGraph()) | |
1754 >>> pred, dist = nx.goldberg_radzik(G, 0) | |
1755 >>> sorted(pred.items()) | |
1756 [(0, None), (1, 0), (2, 1), (3, 2), (4, 3)] | |
1757 >>> sorted(dist.items()) | |
1758 [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)] | |
1759 | |
1760 >>> G = nx.cycle_graph(5, create_using=nx.DiGraph()) | |
1761 >>> G[1][2]["weight"] = -7 | |
1762 >>> nx.goldberg_radzik(G, 0) | |
1763 Traceback (most recent call last): | |
1764 ... | |
1765 networkx.exception.NetworkXUnbounded: Negative cost cycle detected. | |
1766 | |
1767 Notes | |
1768 ----- | |
1769 Edge weight attributes must be numerical. | |
1770 Distances are calculated as sums of weighted edges traversed. | |
1771 | |
1772 The dictionaries returned only have keys for nodes reachable from | |
1773 the source. | |
1774 | |
1775 In the case where the (di)graph is not connected, if a component | |
1776 not containing the source contains a negative cost (di)cycle, it | |
1777 will not be detected. | |
1778 | |
1779 """ | |
1780 if source not in G: | |
1781 raise nx.NodeNotFound(f"Node {source} is not found in the graph") | |
1782 weight = _weight_function(G, weight) | |
1783 if any(weight(u, v, d) < 0 for u, v, d in nx.selfloop_edges(G, data=True)): | |
1784 raise nx.NetworkXUnbounded("Negative cost cycle detected.") | |
1785 | |
1786 if len(G) == 1: | |
1787 return {source: None}, {source: 0} | |
1788 | |
1789 if G.is_directed(): | |
1790 G_succ = G.succ | |
1791 else: | |
1792 G_succ = G.adj | |
1793 | |
1794 inf = float("inf") | |
1795 d = {u: inf for u in G} | |
1796 d[source] = 0 | |
1797 pred = {source: None} | |
1798 | |
1799 def topo_sort(relabeled): | |
1800 """Topologically sort nodes relabeled in the previous round and detect | |
1801 negative cycles. | |
1802 """ | |
1803 # List of nodes to scan in this round. Denoted by A in Goldberg and | |
1804 # Radzik's paper. | |
1805 to_scan = [] | |
1806 # In the DFS in the loop below, neg_count records for each node the | |
1807 # number of edges of negative reduced costs on the path from a DFS root | |
1808 # to the node in the DFS forest. The reduced cost of an edge (u, v) is | |
1809 # defined as d[u] + weight[u][v] - d[v]. | |
1810 # | |
1811 # neg_count also doubles as the DFS visit marker array. | |
1812 neg_count = {} | |
1813 for u in relabeled: | |
1814 # Skip visited nodes. | |
1815 if u in neg_count: | |
1816 continue | |
1817 d_u = d[u] | |
1818 # Skip nodes without out-edges of negative reduced costs. | |
1819 if all(d_u + weight(u, v, e) >= d[v] for v, e in G_succ[u].items()): | |
1820 continue | |
1821 # Nonrecursive DFS that inserts nodes reachable from u via edges of | |
1822 # nonpositive reduced costs into to_scan in (reverse) topological | |
1823 # order. | |
1824 stack = [(u, iter(G_succ[u].items()))] | |
1825 in_stack = {u} | |
1826 neg_count[u] = 0 | |
1827 while stack: | |
1828 u, it = stack[-1] | |
1829 try: | |
1830 v, e = next(it) | |
1831 except StopIteration: | |
1832 to_scan.append(u) | |
1833 stack.pop() | |
1834 in_stack.remove(u) | |
1835 continue | |
1836 t = d[u] + weight(u, v, e) | |
1837 d_v = d[v] | |
1838 if t <= d_v: | |
1839 is_neg = t < d_v | |
1840 d[v] = t | |
1841 pred[v] = u | |
1842 if v not in neg_count: | |
1843 neg_count[v] = neg_count[u] + int(is_neg) | |
1844 stack.append((v, iter(G_succ[v].items()))) | |
1845 in_stack.add(v) | |
1846 elif v in in_stack and neg_count[u] + int(is_neg) > neg_count[v]: | |
1847 # (u, v) is a back edge, and the cycle formed by the | |
1848 # path v to u and (u, v) contains at least one edge of | |
1849 # negative reduced cost. The cycle must be of negative | |
1850 # cost. | |
1851 raise nx.NetworkXUnbounded("Negative cost cycle detected.") | |
1852 to_scan.reverse() | |
1853 return to_scan | |
1854 | |
1855 def relax(to_scan): | |
1856 """Relax out-edges of relabeled nodes. | |
1857 """ | |
1858 relabeled = set() | |
1859 # Scan nodes in to_scan in topological order and relax incident | |
1860 # out-edges. Add the relabled nodes to labeled. | |
1861 for u in to_scan: | |
1862 d_u = d[u] | |
1863 for v, e in G_succ[u].items(): | |
1864 w_e = weight(u, v, e) | |
1865 if d_u + w_e < d[v]: | |
1866 d[v] = d_u + w_e | |
1867 pred[v] = u | |
1868 relabeled.add(v) | |
1869 return relabeled | |
1870 | |
1871 # Set of nodes relabled in the last round of scan operations. Denoted by B | |
1872 # in Goldberg and Radzik's paper. | |
1873 relabeled = {source} | |
1874 | |
1875 while relabeled: | |
1876 to_scan = topo_sort(relabeled) | |
1877 relabeled = relax(to_scan) | |
1878 | |
1879 d = {u: d[u] for u in pred} | |
1880 return pred, d | |
1881 | |
1882 | |
1883 def negative_edge_cycle(G, weight="weight", heuristic=True): | |
1884 """Returns True if there exists a negative edge cycle anywhere in G. | |
1885 | |
1886 Parameters | |
1887 ---------- | |
1888 G : NetworkX graph | |
1889 | |
1890 weight : string or function | |
1891 If this is a string, then edge weights will be accessed via the | |
1892 edge attribute with this key (that is, the weight of the edge | |
1893 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no | |
1894 such edge attribute exists, the weight of the edge is assumed to | |
1895 be one. | |
1896 | |
1897 If this is a function, the weight of an edge is the value | |
1898 returned by the function. The function must accept exactly three | |
1899 positional arguments: the two endpoints of an edge and the | |
1900 dictionary of edge attributes for that edge. The function must | |
1901 return a number. | |
1902 | |
1903 heuristic : bool | |
1904 Determines whether to use a heuristic to early detect negative | |
1905 cycles at a negligible cost. In case of graphs with a negative cycle, | |
1906 the performance of detection increases by at least an order of magnitude. | |
1907 | |
1908 Returns | |
1909 ------- | |
1910 negative_cycle : bool | |
1911 True if a negative edge cycle exists, otherwise False. | |
1912 | |
1913 Examples | |
1914 -------- | |
1915 >>> G = nx.cycle_graph(5, create_using=nx.DiGraph()) | |
1916 >>> print(nx.negative_edge_cycle(G)) | |
1917 False | |
1918 >>> G[1][2]["weight"] = -7 | |
1919 >>> print(nx.negative_edge_cycle(G)) | |
1920 True | |
1921 | |
1922 Notes | |
1923 ----- | |
1924 Edge weight attributes must be numerical. | |
1925 Distances are calculated as sums of weighted edges traversed. | |
1926 | |
1927 This algorithm uses bellman_ford_predecessor_and_distance() but finds | |
1928 negative cycles on any component by first adding a new node connected to | |
1929 every node, and starting bellman_ford_predecessor_and_distance on that | |
1930 node. It then removes that extra node. | |
1931 """ | |
1932 newnode = generate_unique_node() | |
1933 G.add_edges_from([(newnode, n) for n in G]) | |
1934 | |
1935 try: | |
1936 bellman_ford_predecessor_and_distance(G, newnode, weight, heuristic=heuristic) | |
1937 except nx.NetworkXUnbounded: | |
1938 return True | |
1939 finally: | |
1940 G.remove_node(newnode) | |
1941 return False | |
1942 | |
1943 | |
1944 def bidirectional_dijkstra(G, source, target, weight="weight"): | |
1945 r"""Dijkstra's algorithm for shortest paths using bidirectional search. | |
1946 | |
1947 Parameters | |
1948 ---------- | |
1949 G : NetworkX graph | |
1950 | |
1951 source : node | |
1952 Starting node. | |
1953 | |
1954 target : node | |
1955 Ending node. | |
1956 | |
1957 weight : string or function | |
1958 If this is a string, then edge weights will be accessed via the | |
1959 edge attribute with this key (that is, the weight of the edge | |
1960 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no | |
1961 such edge attribute exists, the weight of the edge is assumed to | |
1962 be one. | |
1963 | |
1964 If this is a function, the weight of an edge is the value | |
1965 returned by the function. The function must accept exactly three | |
1966 positional arguments: the two endpoints of an edge and the | |
1967 dictionary of edge attributes for that edge. The function must | |
1968 return a number. | |
1969 | |
1970 Returns | |
1971 ------- | |
1972 length, path : number and list | |
1973 length is the distance from source to target. | |
1974 path is a list of nodes on a path from source to target. | |
1975 | |
1976 Raises | |
1977 ------ | |
1978 NodeNotFound | |
1979 If either `source` or `target` is not in `G`. | |
1980 | |
1981 NetworkXNoPath | |
1982 If no path exists between source and target. | |
1983 | |
1984 Examples | |
1985 -------- | |
1986 >>> G = nx.path_graph(5) | |
1987 >>> length, path = nx.bidirectional_dijkstra(G, 0, 4) | |
1988 >>> print(length) | |
1989 4 | |
1990 >>> print(path) | |
1991 [0, 1, 2, 3, 4] | |
1992 | |
1993 Notes | |
1994 ----- | |
1995 Edge weight attributes must be numerical. | |
1996 Distances are calculated as sums of weighted edges traversed. | |
1997 | |
1998 In practice bidirectional Dijkstra is much more than twice as fast as | |
1999 ordinary Dijkstra. | |
2000 | |
2001 Ordinary Dijkstra expands nodes in a sphere-like manner from the | |
2002 source. The radius of this sphere will eventually be the length | |
2003 of the shortest path. Bidirectional Dijkstra will expand nodes | |
2004 from both the source and the target, making two spheres of half | |
2005 this radius. Volume of the first sphere is `\pi*r*r` while the | |
2006 others are `2*\pi*r/2*r/2`, making up half the volume. | |
2007 | |
2008 This algorithm is not guaranteed to work if edge weights | |
2009 are negative or are floating point numbers | |
2010 (overflows and roundoff errors can cause problems). | |
2011 | |
2012 See Also | |
2013 -------- | |
2014 shortest_path | |
2015 shortest_path_length | |
2016 """ | |
2017 if source not in G or target not in G: | |
2018 msg = f"Either source {source} or target {target} is not in G" | |
2019 raise nx.NodeNotFound(msg) | |
2020 | |
2021 if source == target: | |
2022 return (0, [source]) | |
2023 | |
2024 weight = _weight_function(G, weight) | |
2025 push = heappush | |
2026 pop = heappop | |
2027 # Init: [Forward, Backward] | |
2028 dists = [{}, {}] # dictionary of final distances | |
2029 paths = [{source: [source]}, {target: [target]}] # dictionary of paths | |
2030 fringe = [[], []] # heap of (distance, node) for choosing node to expand | |
2031 seen = [{source: 0}, {target: 0}] # dict of distances to seen nodes | |
2032 c = count() | |
2033 # initialize fringe heap | |
2034 push(fringe[0], (0, next(c), source)) | |
2035 push(fringe[1], (0, next(c), target)) | |
2036 # neighs for extracting correct neighbor information | |
2037 if G.is_directed(): | |
2038 neighs = [G._succ, G._pred] | |
2039 else: | |
2040 neighs = [G._adj, G._adj] | |
2041 # variables to hold shortest discovered path | |
2042 # finaldist = 1e30000 | |
2043 finalpath = [] | |
2044 dir = 1 | |
2045 while fringe[0] and fringe[1]: | |
2046 # choose direction | |
2047 # dir == 0 is forward direction and dir == 1 is back | |
2048 dir = 1 - dir | |
2049 # extract closest to expand | |
2050 (dist, _, v) = pop(fringe[dir]) | |
2051 if v in dists[dir]: | |
2052 # Shortest path to v has already been found | |
2053 continue | |
2054 # update distance | |
2055 dists[dir][v] = dist # equal to seen[dir][v] | |
2056 if v in dists[1 - dir]: | |
2057 # if we have scanned v in both directions we are done | |
2058 # we have now discovered the shortest path | |
2059 return (finaldist, finalpath) | |
2060 | |
2061 for w, d in neighs[dir][v].items(): | |
2062 if dir == 0: # forward | |
2063 vwLength = dists[dir][v] + weight(v, w, d) | |
2064 else: # back, must remember to change v,w->w,v | |
2065 vwLength = dists[dir][v] + weight(w, v, d) | |
2066 if w in dists[dir]: | |
2067 if vwLength < dists[dir][w]: | |
2068 raise ValueError("Contradictory paths found: negative weights?") | |
2069 elif w not in seen[dir] or vwLength < seen[dir][w]: | |
2070 # relaxing | |
2071 seen[dir][w] = vwLength | |
2072 push(fringe[dir], (vwLength, next(c), w)) | |
2073 paths[dir][w] = paths[dir][v] + [w] | |
2074 if w in seen[0] and w in seen[1]: | |
2075 # see if this path is better than than the already | |
2076 # discovered shortest path | |
2077 totaldist = seen[0][w] + seen[1][w] | |
2078 if finalpath == [] or finaldist > totaldist: | |
2079 finaldist = totaldist | |
2080 revpath = paths[1][w][:] | |
2081 revpath.reverse() | |
2082 finalpath = paths[0][w] + revpath[1:] | |
2083 raise nx.NetworkXNoPath(f"No path between {source} and {target}.") | |
2084 | |
2085 | |
2086 def johnson(G, weight="weight"): | |
2087 r"""Uses Johnson's Algorithm to compute shortest paths. | |
2088 | |
2089 Johnson's Algorithm finds a shortest path between each pair of | |
2090 nodes in a weighted graph even if negative weights are present. | |
2091 | |
2092 Parameters | |
2093 ---------- | |
2094 G : NetworkX graph | |
2095 | |
2096 weight : string or function | |
2097 If this is a string, then edge weights will be accessed via the | |
2098 edge attribute with this key (that is, the weight of the edge | |
2099 joining `u` to `v` will be ``G.edges[u, v][weight]``). If no | |
2100 such edge attribute exists, the weight of the edge is assumed to | |
2101 be one. | |
2102 | |
2103 If this is a function, the weight of an edge is the value | |
2104 returned by the function. The function must accept exactly three | |
2105 positional arguments: the two endpoints of an edge and the | |
2106 dictionary of edge attributes for that edge. The function must | |
2107 return a number. | |
2108 | |
2109 Returns | |
2110 ------- | |
2111 distance : dictionary | |
2112 Dictionary, keyed by source and target, of shortest paths. | |
2113 | |
2114 Raises | |
2115 ------ | |
2116 NetworkXError | |
2117 If given graph is not weighted. | |
2118 | |
2119 Examples | |
2120 -------- | |
2121 >>> graph = nx.DiGraph() | |
2122 >>> graph.add_weighted_edges_from( | |
2123 ... [("0", "3", 3), ("0", "1", -5), ("0", "2", 2), ("1", "2", 4), ("2", "3", 1)] | |
2124 ... ) | |
2125 >>> paths = nx.johnson(graph, weight="weight") | |
2126 >>> paths["0"]["2"] | |
2127 ['0', '1', '2'] | |
2128 | |
2129 Notes | |
2130 ----- | |
2131 Johnson's algorithm is suitable even for graphs with negative weights. It | |
2132 works by using the Bellman–Ford algorithm to compute a transformation of | |
2133 the input graph that removes all negative weights, allowing Dijkstra's | |
2134 algorithm to be used on the transformed graph. | |
2135 | |
2136 The time complexity of this algorithm is $O(n^2 \log n + n m)$, | |
2137 where $n$ is the number of nodes and $m$ the number of edges in the | |
2138 graph. For dense graphs, this may be faster than the Floyd–Warshall | |
2139 algorithm. | |
2140 | |
2141 See Also | |
2142 -------- | |
2143 floyd_warshall_predecessor_and_distance | |
2144 floyd_warshall_numpy | |
2145 all_pairs_shortest_path | |
2146 all_pairs_shortest_path_length | |
2147 all_pairs_dijkstra_path | |
2148 bellman_ford_predecessor_and_distance | |
2149 all_pairs_bellman_ford_path | |
2150 all_pairs_bellman_ford_path_length | |
2151 | |
2152 """ | |
2153 if not nx.is_weighted(G, weight=weight): | |
2154 raise nx.NetworkXError("Graph is not weighted.") | |
2155 | |
2156 dist = {v: 0 for v in G} | |
2157 pred = {v: [] for v in G} | |
2158 weight = _weight_function(G, weight) | |
2159 | |
2160 # Calculate distance of shortest paths | |
2161 dist_bellman = _bellman_ford(G, list(G), weight, pred=pred, dist=dist) | |
2162 | |
2163 # Update the weight function to take into account the Bellman--Ford | |
2164 # relaxation distances. | |
2165 def new_weight(u, v, d): | |
2166 return weight(u, v, d) + dist_bellman[u] - dist_bellman[v] | |
2167 | |
2168 def dist_path(v): | |
2169 paths = {v: [v]} | |
2170 _dijkstra(G, v, new_weight, paths=paths) | |
2171 return paths | |
2172 | |
2173 return {v: dist_path(v) for v in G} |