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
1from heapq import heappop, heappush
2from itertools import count
4import networkx as nx
5from networkx.algorithms.shortest_paths.weighted import _weight_function
6from networkx.utils import not_implemented_for, pairwise
8__all__ = [
9 "all_simple_paths",
10 "is_simple_path",
11 "shortest_simple_paths",
12 "all_simple_edge_paths",
13]
16@nx._dispatchable
17def is_simple_path(G, nodes):
18 """Returns True if and only if `nodes` form a simple path in `G`.
20 A *simple path* in a graph is a nonempty sequence of nodes in which
21 no node appears more than once in the sequence, and each adjacent
22 pair of nodes in the sequence is adjacent in the graph.
24 Parameters
25 ----------
26 G : graph
27 A NetworkX graph.
28 nodes : list
29 A list of one or more nodes in the graph `G`.
31 Returns
32 -------
33 bool
34 Whether the given list of nodes represents a simple path in `G`.
36 Notes
37 -----
38 An empty list of nodes is not a path but a list of one node is a
39 path. Here's an explanation why.
41 This function operates on *node paths*. One could also consider
42 *edge paths*. There is a bijection between node paths and edge
43 paths.
45 The *length of a path* is the number of edges in the path, so a list
46 of nodes of length *n* corresponds to a path of length *n* - 1.
47 Thus the smallest edge path would be a list of zero edges, the empty
48 path. This corresponds to a list of one node.
50 To convert between a node path and an edge path, you can use code
51 like the following::
53 >>> from networkx.utils import pairwise
54 >>> nodes = [0, 1, 2, 3]
55 >>> edges = list(pairwise(nodes))
56 >>> edges
57 [(0, 1), (1, 2), (2, 3)]
58 >>> nodes = [edges[0][0]] + [v for u, v in edges]
59 >>> nodes
60 [0, 1, 2, 3]
62 Examples
63 --------
64 >>> G = nx.cycle_graph(4)
65 >>> nx.is_simple_path(G, [2, 3, 0])
66 True
67 >>> nx.is_simple_path(G, [0, 2])
68 False
70 """
71 # The empty list is not a valid path. Could also return
72 # NetworkXPointlessConcept here.
73 if len(nodes) == 0:
74 return False
76 # If the list is a single node, just check that the node is actually
77 # in the graph.
78 if len(nodes) == 1:
79 return nodes[0] in G
81 # check that all nodes in the list are in the graph, if at least one
82 # is not in the graph, then this is not a simple path
83 if not all(n in G for n in nodes):
84 return False
86 # If the list contains repeated nodes, then it's not a simple path
87 if len(set(nodes)) != len(nodes):
88 return False
90 # Test that each adjacent pair of nodes is adjacent.
91 return all(v in G[u] for u, v in pairwise(nodes))
94@nx._dispatchable
95def all_simple_paths(G, source, target, cutoff=None):
96 """Generate all simple paths in the graph G from source to target.
98 A simple path is a path with no repeated nodes.
100 Parameters
101 ----------
102 G : NetworkX graph
104 source : node
105 Starting node for path
107 target : nodes
108 Single node or iterable of nodes at which to end path
110 cutoff : integer, optional
111 Depth to stop the search. Only paths with length <= `cutoff` are returned.
112 where the mathematical "length of a path" is `len(path) -1` (number of edges).
114 Returns
115 -------
116 path_generator: generator
117 A generator that produces lists of simple paths. If there are no paths
118 between the source and target within the given cutoff the generator
119 produces no output. If it is possible to traverse the same sequence of
120 nodes in multiple ways, namely through parallel edges, then it will be
121 returned multiple times (once for each viable edge combination).
123 Examples
124 --------
125 This iterator generates lists of nodes::
127 >>> G = nx.complete_graph(4)
128 >>> for path in nx.all_simple_paths(G, source=0, target=3):
129 ... print(path)
130 ...
131 [0, 1, 2, 3]
132 [0, 1, 3]
133 [0, 2, 1, 3]
134 [0, 2, 3]
135 [0, 3]
137 You can generate only those paths that are shorter than a certain
138 length by using the `cutoff` keyword argument::
140 >>> paths = nx.all_simple_paths(G, source=0, target=3, cutoff=2)
141 >>> print(list(paths))
142 [[0, 1, 3], [0, 2, 3], [0, 3]]
144 To get each path as the corresponding list of edges, you can use the
145 :func:`networkx.utils.pairwise` helper function::
147 >>> paths = nx.all_simple_paths(G, source=0, target=3)
148 >>> for path in map(nx.utils.pairwise, paths):
149 ... print(list(path))
150 [(0, 1), (1, 2), (2, 3)]
151 [(0, 1), (1, 3)]
152 [(0, 2), (2, 1), (1, 3)]
153 [(0, 2), (2, 3)]
154 [(0, 3)]
156 Pass an iterable of nodes as target to generate all paths ending in any of several nodes::
158 >>> G = nx.complete_graph(4)
159 >>> for path in nx.all_simple_paths(G, source=0, target=[3, 2]):
160 ... print(path)
161 ...
162 [0, 1, 2]
163 [0, 1, 2, 3]
164 [0, 1, 3]
165 [0, 1, 3, 2]
166 [0, 2]
167 [0, 2, 1, 3]
168 [0, 2, 3]
169 [0, 3]
170 [0, 3, 1, 2]
171 [0, 3, 2]
173 The singleton path from ``source`` to itself is considered a simple path and is
174 included in the results:
176 >>> G = nx.empty_graph(5)
177 >>> list(nx.all_simple_paths(G, source=0, target=0))
178 [[0]]
180 >>> G = nx.path_graph(3)
181 >>> list(nx.all_simple_paths(G, source=0, target={0, 1, 2}))
182 [[0], [0, 1], [0, 1, 2]]
184 Iterate over each path from the root nodes to the leaf nodes in a
185 directed acyclic graph using a functional programming approach::
187 >>> from itertools import chain
188 >>> from itertools import product
189 >>> from itertools import starmap
190 >>> from functools import partial
191 >>>
192 >>> chaini = chain.from_iterable
193 >>>
194 >>> G = nx.DiGraph([(0, 1), (1, 2), (0, 3), (3, 2)])
195 >>> roots = (v for v, d in G.in_degree() if d == 0)
196 >>> leaves = (v for v, d in G.out_degree() if d == 0)
197 >>> all_paths = partial(nx.all_simple_paths, G)
198 >>> list(chaini(starmap(all_paths, product(roots, leaves))))
199 [[0, 1, 2], [0, 3, 2]]
201 The same list computed using an iterative approach::
203 >>> G = nx.DiGraph([(0, 1), (1, 2), (0, 3), (3, 2)])
204 >>> roots = (v for v, d in G.in_degree() if d == 0)
205 >>> leaves = (v for v, d in G.out_degree() if d == 0)
206 >>> all_paths = []
207 >>> for root in roots:
208 ... for leaf in leaves:
209 ... paths = nx.all_simple_paths(G, root, leaf)
210 ... all_paths.extend(paths)
211 >>> all_paths
212 [[0, 1, 2], [0, 3, 2]]
214 Iterate over each path from the root nodes to the leaf nodes in a
215 directed acyclic graph passing all leaves together to avoid unnecessary
216 compute::
218 >>> G = nx.DiGraph([(0, 1), (2, 1), (1, 3), (1, 4)])
219 >>> roots = (v for v, d in G.in_degree() if d == 0)
220 >>> leaves = [v for v, d in G.out_degree() if d == 0]
221 >>> all_paths = []
222 >>> for root in roots:
223 ... paths = nx.all_simple_paths(G, root, leaves)
224 ... all_paths.extend(paths)
225 >>> all_paths
226 [[0, 1, 3], [0, 1, 4], [2, 1, 3], [2, 1, 4]]
228 If parallel edges offer multiple ways to traverse a given sequence of
229 nodes, this sequence of nodes will be returned multiple times:
231 >>> G = nx.MultiDiGraph([(0, 1), (0, 1), (1, 2)])
232 >>> list(nx.all_simple_paths(G, 0, 2))
233 [[0, 1, 2], [0, 1, 2]]
235 Notes
236 -----
237 This algorithm uses a modified depth-first search to generate the
238 paths [1]_. A single path can be found in $O(V+E)$ time but the
239 number of simple paths in a graph can be very large, e.g. $O(n!)$ in
240 the complete graph of order $n$.
242 This function does not check that a path exists between `source` and
243 `target`. For large graphs, this may result in very long runtimes.
244 Consider using `has_path` to check that a path exists between `source` and
245 `target` before calling this function on large graphs.
247 References
248 ----------
249 .. [1] R. Sedgewick, "Algorithms in C, Part 5: Graph Algorithms",
250 Addison Wesley Professional, 3rd ed., 2001.
252 See Also
253 --------
254 all_shortest_paths, shortest_path, has_path
256 """
257 for edge_path in all_simple_edge_paths(G, source, target, cutoff):
258 yield [source] + [edge[1] for edge in edge_path]
261@nx._dispatchable
262def all_simple_edge_paths(G, source, target, cutoff=None):
263 """Generate lists of edges for all simple paths in G from source to target.
265 A simple path is a path with no repeated nodes.
267 Parameters
268 ----------
269 G : NetworkX graph
271 source : node
272 Starting node for path
274 target : nodes
275 Single node or iterable of nodes at which to end path
277 cutoff : integer, optional
278 Depth to stop the search. Only paths with length <= `cutoff` are returned.
279 Note that the length of an edge path is the number of edges.
281 Returns
282 -------
283 path_generator: generator
284 A generator that produces lists of simple paths. If there are no paths
285 between the source and target within the given cutoff the generator
286 produces no output.
287 For multigraphs, the list of edges have elements of the form `(u,v,k)`.
288 Where `k` corresponds to the edge key.
290 Examples
291 --------
293 Print the simple path edges of a Graph::
295 >>> g = nx.Graph([(1, 2), (2, 4), (1, 3), (3, 4)])
296 >>> for path in sorted(nx.all_simple_edge_paths(g, 1, 4)):
297 ... print(path)
298 [(1, 2), (2, 4)]
299 [(1, 3), (3, 4)]
301 Print the simple path edges of a MultiGraph. Returned edges come with
302 their associated keys::
304 >>> mg = nx.MultiGraph()
305 >>> mg.add_edge(1, 2, key="k0")
306 'k0'
307 >>> mg.add_edge(1, 2, key="k1")
308 'k1'
309 >>> mg.add_edge(2, 3, key="k0")
310 'k0'
311 >>> for path in sorted(nx.all_simple_edge_paths(mg, 1, 3)):
312 ... print(path)
313 [(1, 2, 'k0'), (2, 3, 'k0')]
314 [(1, 2, 'k1'), (2, 3, 'k0')]
316 When ``source`` is one of the targets, the empty path starting and ending at
317 ``source`` without traversing any edge is considered a valid simple edge path
318 and is included in the results:
320 >>> G = nx.Graph()
321 >>> G.add_node(0)
322 >>> paths = list(nx.all_simple_edge_paths(G, 0, 0))
323 >>> for path in paths:
324 ... print(path)
325 []
326 >>> len(paths)
327 1
329 You can use the `cutoff` parameter to only generate paths that are
330 shorter than a certain length:
332 >>> g = nx.Graph([(1, 2), (2, 3), (3, 4), (4, 5), (1, 4), (1, 5)])
333 >>> for path in sorted(nx.all_simple_edge_paths(g, 1, 5)):
334 ... print(path)
335 [(1, 2), (2, 3), (3, 4), (4, 5)]
336 [(1, 4), (4, 5)]
337 [(1, 5)]
338 >>> for path in sorted(nx.all_simple_edge_paths(g, 1, 5, cutoff=1)):
339 ... print(path)
340 [(1, 5)]
341 >>> for path in sorted(nx.all_simple_edge_paths(g, 1, 5, cutoff=2)):
342 ... print(path)
343 [(1, 4), (4, 5)]
344 [(1, 5)]
346 Notes
347 -----
348 This algorithm uses a modified depth-first search to generate the
349 paths [1]_. A single path can be found in $O(V+E)$ time but the
350 number of simple paths in a graph can be very large, e.g. $O(n!)$ in
351 the complete graph of order $n$.
353 References
354 ----------
355 .. [1] R. Sedgewick, "Algorithms in C, Part 5: Graph Algorithms",
356 Addison Wesley Professional, 3rd ed., 2001.
358 See Also
359 --------
360 all_shortest_paths, shortest_path, all_simple_paths
362 """
363 if source not in G:
364 raise nx.NodeNotFound(f"source node {source} not in graph")
366 if target in G:
367 targets = {target}
368 else:
369 try:
370 targets = set(target)
371 except TypeError as err:
372 raise nx.NodeNotFound(f"target node {target} not in graph") from err
374 cutoff = cutoff if cutoff is not None else len(G) - 1
376 if cutoff >= 0 and targets:
377 yield from _all_simple_edge_paths(G, source, targets, cutoff)
380def _all_simple_edge_paths(G, source, targets, cutoff):
381 # We simulate recursion with a stack, keeping the current path being explored
382 # and the outgoing edge iterators at each point in the stack.
383 # To avoid unnecessary checks, the loop is structured in a way such that a path
384 # is considered for yielding only after a new node/edge is added.
385 # We bootstrap the search by adding a dummy iterator to the stack that only yields
386 # a dummy edge to source (so that the trivial path has a chance of being included).
388 get_edges = (
389 (lambda node: G.edges(node, keys=True))
390 if G.is_multigraph()
391 else (lambda node: G.edges(node))
392 )
394 # The current_path is a dictionary that maps nodes in the path to the edge that was
395 # used to enter that node (instead of a list of edges) because we want both a fast
396 # membership test for nodes in the path and the preservation of insertion order.
397 current_path = {None: None}
398 stack = [iter([(None, source)])]
400 while stack:
401 # 1. Try to extend the current path.
402 next_edge = next((e for e in stack[-1] if e[1] not in current_path), None)
403 if next_edge is None:
404 # All edges of the last node in the current path have been explored.
405 stack.pop()
406 current_path.popitem()
407 continue
408 previous_node, next_node, *_ = next_edge
410 # 2. Check if we've reached a target.
411 if next_node in targets:
412 yield (list(current_path.values()) + [next_edge])[2:] # remove dummy edge
414 # 3. Only expand the search through the next node if it makes sense.
415 if len(current_path) - 1 < cutoff and (
416 targets - current_path.keys() - {next_node}
417 ):
418 current_path[next_node] = next_edge
419 stack.append(iter(get_edges(next_node)))
422@not_implemented_for("multigraph")
423@nx._dispatchable(edge_attrs="weight")
424def shortest_simple_paths(G, source, target, weight=None):
425 """Generate all simple paths in the graph G from source to target,
426 starting from shortest ones.
428 A simple path is a path with no repeated nodes.
430 If a weighted shortest path search is to be used, no negative weights
431 are allowed.
433 Parameters
434 ----------
435 G : NetworkX graph
437 source : node
438 Starting node for path
440 target : node
441 Ending node for path
443 weight : string or function
444 If it is a string, it is the name of the edge attribute to be
445 used as a weight.
447 If it is a function, the weight of an edge is the value returned
448 by the function. The function must accept exactly three positional
449 arguments: the two endpoints of an edge and the dictionary of edge
450 attributes for that edge. The function must return a number or None.
451 The weight function can be used to hide edges by returning None.
452 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
453 will find the shortest red path.
455 If None all edges are considered to have unit weight. Default
456 value None.
458 Returns
459 -------
460 path_generator: generator
461 A generator that produces lists of simple paths, in order from
462 shortest to longest.
464 Raises
465 ------
466 NetworkXNoPath
467 If no path exists between source and target.
469 NetworkXError
470 If source or target nodes are not in the input graph.
472 NetworkXNotImplemented
473 If the input graph is a Multi[Di]Graph.
475 Examples
476 --------
478 >>> G = nx.cycle_graph(7)
479 >>> paths = list(nx.shortest_simple_paths(G, 0, 3))
480 >>> print(paths)
481 [[0, 1, 2, 3], [0, 6, 5, 4, 3]]
483 You can use this function to efficiently compute the k shortest/best
484 paths between two nodes.
486 >>> from itertools import islice
487 >>> def k_shortest_paths(G, source, target, k, weight=None):
488 ... return list(
489 ... islice(nx.shortest_simple_paths(G, source, target, weight=weight), k)
490 ... )
491 >>> for path in k_shortest_paths(G, 0, 3, 2):
492 ... print(path)
493 [0, 1, 2, 3]
494 [0, 6, 5, 4, 3]
496 Notes
497 -----
498 This procedure is based on algorithm by Jin Y. Yen [1]_. Finding
499 the first $K$ paths requires $O(KN^3)$ operations.
501 See Also
502 --------
503 all_shortest_paths
504 shortest_path
505 all_simple_paths
507 References
508 ----------
509 .. [1] Jin Y. Yen, "Finding the K Shortest Loopless Paths in a
510 Network", Management Science, Vol. 17, No. 11, Theory Series
511 (Jul., 1971), pp. 712-716.
513 """
514 if source not in G:
515 raise nx.NodeNotFound(f"source node {source} not in graph")
517 if target not in G:
518 raise nx.NodeNotFound(f"target node {target} not in graph")
520 if weight is None:
521 length_func = len
522 shortest_path_func = _bidirectional_shortest_path
523 else:
524 wt = _weight_function(G, weight)
526 def length_func(path):
527 return sum(
528 wt(u, v, G.get_edge_data(u, v)) for (u, v) in zip(path, path[1:])
529 )
531 shortest_path_func = _bidirectional_dijkstra
533 listA = []
534 listB = PathBuffer()
535 prev_path = None
536 while True:
537 if not prev_path:
538 length, path = shortest_path_func(G, source, target, weight=weight)
539 listB.push(length, path)
540 else:
541 ignore_nodes = set()
542 ignore_edges = set()
543 for i in range(1, len(prev_path)):
544 root = prev_path[:i]
545 root_length = length_func(root)
546 for path in listA:
547 if path[:i] == root:
548 ignore_edges.add((path[i - 1], path[i]))
549 try:
550 length, spur = shortest_path_func(
551 G,
552 root[-1],
553 target,
554 ignore_nodes=ignore_nodes,
555 ignore_edges=ignore_edges,
556 weight=weight,
557 )
558 path = root[:-1] + spur
559 listB.push(root_length + length, path)
560 except nx.NetworkXNoPath:
561 pass
562 ignore_nodes.add(root[-1])
564 if listB:
565 path = listB.pop()
566 yield path
567 listA.append(path)
568 prev_path = path
569 else:
570 break
573class PathBuffer:
574 def __init__(self):
575 self.paths = set()
576 self.sortedpaths = []
577 self.counter = count()
579 def __len__(self):
580 return len(self.sortedpaths)
582 def push(self, cost, path):
583 hashable_path = tuple(path)
584 if hashable_path not in self.paths:
585 heappush(self.sortedpaths, (cost, next(self.counter), path))
586 self.paths.add(hashable_path)
588 def pop(self):
589 (cost, num, path) = heappop(self.sortedpaths)
590 hashable_path = tuple(path)
591 self.paths.remove(hashable_path)
592 return path
595def _bidirectional_shortest_path(
596 G, source, target, ignore_nodes=None, ignore_edges=None, weight=None
597):
598 """Returns the shortest path between source and target ignoring
599 nodes and edges in the containers ignore_nodes and ignore_edges.
601 This is a custom modification of the standard bidirectional shortest
602 path implementation at networkx.algorithms.unweighted
604 Parameters
605 ----------
606 G : NetworkX graph
608 source : node
609 starting node for path
611 target : node
612 ending node for path
614 ignore_nodes : container of nodes
615 nodes to ignore, optional
617 ignore_edges : container of edges
618 edges to ignore, optional
620 weight : None
621 This function accepts a weight argument for convenience of
622 shortest_simple_paths function. It will be ignored.
624 Returns
625 -------
626 path: list
627 List of nodes in a path from source to target.
629 Raises
630 ------
631 NetworkXNoPath
632 If no path exists between source and target.
634 See Also
635 --------
636 shortest_path
638 """
639 # call helper to do the real work
640 results = _bidirectional_pred_succ(G, source, target, ignore_nodes, ignore_edges)
641 pred, succ, w = results
643 # build path from pred+w+succ
644 path = []
645 # from w to target
646 while w is not None:
647 path.append(w)
648 w = succ[w]
649 # from source to w
650 w = pred[path[0]]
651 while w is not None:
652 path.insert(0, w)
653 w = pred[w]
655 return len(path), path
658def _bidirectional_pred_succ(G, source, target, ignore_nodes=None, ignore_edges=None):
659 """Bidirectional shortest path helper.
660 Returns (pred,succ,w) where
661 pred is a dictionary of predecessors from w to the source, and
662 succ is a dictionary of successors from w to the target.
663 """
664 # does BFS from both source and target and meets in the middle
665 if ignore_nodes and (source in ignore_nodes or target in ignore_nodes):
666 raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
667 if target == source:
668 return ({target: None}, {source: None}, source)
670 # handle either directed or undirected
671 if G.is_directed():
672 Gpred = G.predecessors
673 Gsucc = G.successors
674 else:
675 Gpred = G.neighbors
676 Gsucc = G.neighbors
678 # support optional nodes filter
679 if ignore_nodes:
681 def filter_iter(nodes):
682 def iterate(v):
683 for w in nodes(v):
684 if w not in ignore_nodes:
685 yield w
687 return iterate
689 Gpred = filter_iter(Gpred)
690 Gsucc = filter_iter(Gsucc)
692 # support optional edges filter
693 if ignore_edges:
694 if G.is_directed():
696 def filter_pred_iter(pred_iter):
697 def iterate(v):
698 for w in pred_iter(v):
699 if (w, v) not in ignore_edges:
700 yield w
702 return iterate
704 def filter_succ_iter(succ_iter):
705 def iterate(v):
706 for w in succ_iter(v):
707 if (v, w) not in ignore_edges:
708 yield w
710 return iterate
712 Gpred = filter_pred_iter(Gpred)
713 Gsucc = filter_succ_iter(Gsucc)
715 else:
717 def filter_iter(nodes):
718 def iterate(v):
719 for w in nodes(v):
720 if (v, w) not in ignore_edges and (w, v) not in ignore_edges:
721 yield w
723 return iterate
725 Gpred = filter_iter(Gpred)
726 Gsucc = filter_iter(Gsucc)
728 # predecessor and successors in search
729 pred = {source: None}
730 succ = {target: None}
732 # initialize fringes, start with forward
733 forward_fringe = [source]
734 reverse_fringe = [target]
736 while forward_fringe and reverse_fringe:
737 if len(forward_fringe) <= len(reverse_fringe):
738 this_level = forward_fringe
739 forward_fringe = []
740 for v in this_level:
741 for w in Gsucc(v):
742 if w not in pred:
743 forward_fringe.append(w)
744 pred[w] = v
745 if w in succ:
746 # found path
747 return pred, succ, w
748 else:
749 this_level = reverse_fringe
750 reverse_fringe = []
751 for v in this_level:
752 for w in Gpred(v):
753 if w not in succ:
754 succ[w] = v
755 reverse_fringe.append(w)
756 if w in pred:
757 # found path
758 return pred, succ, w
760 raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
763def _bidirectional_dijkstra(
764 G, source, target, weight="weight", ignore_nodes=None, ignore_edges=None
765):
766 """Dijkstra's algorithm for shortest paths using bidirectional search.
768 This function returns the shortest path between source and target
769 ignoring nodes and edges in the containers ignore_nodes and
770 ignore_edges.
772 This is a custom modification of the standard Dijkstra bidirectional
773 shortest path implementation at networkx.algorithms.weighted
775 Parameters
776 ----------
777 G : NetworkX graph
779 source : node
780 Starting node.
782 target : node
783 Ending node.
785 weight: string, function, optional (default='weight')
786 Edge data key or weight function corresponding to the edge weight
787 If this is a function, the weight of an edge is the value
788 returned by the function. The function must accept exactly three
789 positional arguments: the two endpoints of an edge and the
790 dictionary of edge attributes for that edge. The function must
791 return a number or None to indicate a hidden edge.
793 ignore_nodes : container of nodes
794 nodes to ignore, optional
796 ignore_edges : container of edges
797 edges to ignore, optional
799 Returns
800 -------
801 length : number
802 Shortest path length.
804 Returns a tuple of two dictionaries keyed by node.
805 The first dictionary stores distance from the source.
806 The second stores the path from the source to that node.
808 Raises
809 ------
810 NetworkXNoPath
811 If no path exists between source and target.
813 Notes
814 -----
815 Edge weight attributes must be numerical.
816 Distances are calculated as sums of weighted edges traversed.
818 The weight function can be used to hide edges by returning None.
819 So ``weight = lambda u, v, d: 1 if d['color']=="red" else None``
820 will find the shortest red path.
822 In practice bidirectional Dijkstra is much more than twice as fast as
823 ordinary Dijkstra.
825 Ordinary Dijkstra expands nodes in a sphere-like manner from the
826 source. The radius of this sphere will eventually be the length
827 of the shortest path. Bidirectional Dijkstra will expand nodes
828 from both the source and the target, making two spheres of half
829 this radius. Volume of the first sphere is pi*r*r while the
830 others are 2*pi*r/2*r/2, making up half the volume.
832 This algorithm is not guaranteed to work if edge weights
833 are negative or are floating point numbers
834 (overflows and roundoff errors can cause problems).
836 See Also
837 --------
838 shortest_path
839 shortest_path_length
840 """
841 if ignore_nodes and (source in ignore_nodes or target in ignore_nodes):
842 raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
843 if source == target:
844 if source not in G:
845 raise nx.NodeNotFound(f"Node {source} not in graph")
846 return (0, [source])
848 # handle either directed or undirected
849 if G.is_directed():
850 Gpred = G.predecessors
851 Gsucc = G.successors
852 else:
853 Gpred = G.neighbors
854 Gsucc = G.neighbors
856 # support optional nodes filter
857 if ignore_nodes:
859 def filter_iter(nodes):
860 def iterate(v):
861 for w in nodes(v):
862 if w not in ignore_nodes:
863 yield w
865 return iterate
867 Gpred = filter_iter(Gpred)
868 Gsucc = filter_iter(Gsucc)
870 # support optional edges filter
871 if ignore_edges:
872 if G.is_directed():
874 def filter_pred_iter(pred_iter):
875 def iterate(v):
876 for w in pred_iter(v):
877 if (w, v) not in ignore_edges:
878 yield w
880 return iterate
882 def filter_succ_iter(succ_iter):
883 def iterate(v):
884 for w in succ_iter(v):
885 if (v, w) not in ignore_edges:
886 yield w
888 return iterate
890 Gpred = filter_pred_iter(Gpred)
891 Gsucc = filter_succ_iter(Gsucc)
893 else:
895 def filter_iter(nodes):
896 def iterate(v):
897 for w in nodes(v):
898 if (v, w) not in ignore_edges and (w, v) not in ignore_edges:
899 yield w
901 return iterate
903 Gpred = filter_iter(Gpred)
904 Gsucc = filter_iter(Gsucc)
906 wt = _weight_function(G, weight)
907 # Init: Forward Backward
908 dists = [{}, {}] # dictionary of final distances
909 paths = [{source: [source]}, {target: [target]}] # dictionary of paths
910 fringe = [[], []] # heap of (distance, node) tuples for
911 # extracting next node to expand
912 seen = [{source: 0}, {target: 0}] # dictionary of distances to
913 # nodes seen
914 c = count()
915 # initialize fringe heap
916 heappush(fringe[0], (0, next(c), source))
917 heappush(fringe[1], (0, next(c), target))
918 # neighs for extracting correct neighbor information
919 neighs = [Gsucc, Gpred]
920 # variables to hold shortest discovered path
921 # finaldist = 1e30000
922 finalpath = []
923 dir = 1
924 while fringe[0] and fringe[1]:
925 # choose direction
926 # dir == 0 is forward direction and dir == 1 is back
927 dir = 1 - dir
928 # extract closest to expand
929 (dist, _, v) = heappop(fringe[dir])
930 if v in dists[dir]:
931 # Shortest path to v has already been found
932 continue
933 # update distance
934 dists[dir][v] = dist # equal to seen[dir][v]
935 if v in dists[1 - dir]:
936 # if we have scanned v in both directions we are done
937 # we have now discovered the shortest path
938 return (finaldist, finalpath)
940 for w in neighs[dir](v):
941 if dir == 0: # forward
942 minweight = wt(v, w, G.get_edge_data(v, w))
943 else: # back, must remember to change v,w->w,v
944 minweight = wt(w, v, G.get_edge_data(w, v))
945 if minweight is None:
946 continue
947 vwLength = dists[dir][v] + minweight
949 if w in dists[dir]:
950 if vwLength < dists[dir][w]:
951 raise ValueError("Contradictory paths found: negative weights?")
952 elif w not in seen[dir] or vwLength < seen[dir][w]:
953 # relaxing
954 seen[dir][w] = vwLength
955 heappush(fringe[dir], (vwLength, next(c), w))
956 paths[dir][w] = paths[dir][v] + [w]
957 if w in seen[0] and w in seen[1]:
958 # see if this path is better than the already
959 # discovered shortest path
960 totaldist = seen[0][w] + seen[1][w]
961 if finalpath == [] or finaldist > totaldist:
962 finaldist = totaldist
963 revpath = paths[1][w][:]
964 revpath.reverse()
965 finalpath = paths[0][w] + revpath[1:]
966 raise nx.NetworkXNoPath(f"No path between {source} and {target}.")