Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Shortest path algorithms for unweighted graphs.
3"""
5import operator
7import networkx as nx
9__all__ = [
10 "bidirectional_shortest_path",
11 "single_source_shortest_path",
12 "single_source_shortest_path_length",
13 "single_target_shortest_path",
14 "single_target_shortest_path_length",
15 "all_pairs_shortest_path",
16 "all_pairs_shortest_path_length",
17 "predecessor",
18]
21@nx._dispatchable
22def single_source_shortest_path_length(G, source, cutoff=None):
23 """Compute the shortest path lengths from `source` to all reachable nodes in `G`.
25 Parameters
26 ----------
27 G : NetworkX graph
29 source : node
30 Starting node for path
32 cutoff : integer, optional
33 Depth to stop the search. Only target nodes where the shortest path to
34 this node from the source node contains <= ``cutoff + 1`` nodes will be
35 included in the returned results.
37 Returns
38 -------
39 lengths : dict
40 Dict keyed by node to shortest path length from source node.
42 Examples
43 --------
44 >>> G = nx.path_graph(5)
45 >>> length = nx.single_source_shortest_path_length(G, 0)
46 >>> length[4]
47 4
48 >>> for node in sorted(length):
49 ... print(f"{node}: {length[node]}")
50 0: 0
51 1: 1
52 2: 2
53 3: 3
54 4: 4
56 Only include paths with length less than or equal to the `cutoff` keyword
57 argument:
59 >>> length = nx.single_source_shortest_path_length(G, 0, cutoff=2)
60 >>> for node in sorted(length):
61 ... print(f"{node}: {length[node]}")
62 0: 0
63 1: 1
64 2: 2
66 See Also
67 --------
68 :any:`shortest_path_length` :
69 Shortest path length with specifiable source, target, and weight.
70 :any:`single_source_dijkstra_path_length` :
71 Shortest weighted path length from source with Dijkstra algorithm.
72 :any:`single_source_bellman_ford_path_length` :
73 Shortest weighted path length from source with Bellman-Ford algorithm.
74 """
75 if source not in G:
76 raise nx.NodeNotFound(f"Source {source} is not in G")
77 if cutoff is None:
78 cutoff = float("inf")
79 nextlevel = [source]
80 return dict(_single_shortest_path_length(G._adj, nextlevel, cutoff))
83def _single_shortest_path_length(adj, firstlevel, cutoff):
84 """Yields (node, level) in a breadth first search
86 Shortest Path Length helper function
87 Parameters
88 ----------
89 adj : dict
90 Adjacency dict or view
91 firstlevel : list
92 starting nodes, e.g. [source] or [target]
93 cutoff : int or float
94 level at which we stop the process
95 """
96 seen = set(firstlevel)
97 nextlevel = firstlevel
98 level = 0
99 n = len(adj)
100 for v in nextlevel:
101 yield (v, level)
102 while nextlevel and cutoff > level:
103 level += 1
104 thislevel = nextlevel
105 nextlevel = []
106 for v in thislevel:
107 for w in adj[v]:
108 if w not in seen:
109 seen.add(w)
110 nextlevel.append(w)
111 yield (w, level)
112 if len(seen) == n:
113 return
116@nx._dispatchable
117def single_target_shortest_path_length(G, target, cutoff=None):
118 """Compute the shortest path lengths to target from all reachable nodes.
120 Parameters
121 ----------
122 G : NetworkX graph
124 target : node
125 Target node for path
127 cutoff : integer, optional
128 Depth to stop the search. Only source nodes where the shortest path
129 from this node to the target node contains <= ``cutoff + 1`` nodes will
130 be included in the returned results.
132 Returns
133 -------
134 lengths : dictionary
135 Dictionary, keyed by source, of shortest path lengths.
137 Examples
138 --------
139 >>> G = nx.path_graph(5, create_using=nx.DiGraph())
140 >>> length = nx.single_target_shortest_path_length(G, 4)
141 >>> length[0]
142 4
143 >>> for node in sorted(length):
144 ... print(f"{node}: {length[node]}")
145 0: 4
146 1: 3
147 2: 2
148 3: 1
149 4: 0
151 Only include paths with length less than or equal to the `cutoff` keyword
152 argument:
154 >>> length = nx.single_target_shortest_path_length(G, 4, cutoff=2)
155 >>> for node in sorted(length):
156 ... print(f"{node}: {length[node]}")
157 2: 2
158 3: 1
159 4: 0
161 See Also
162 --------
163 single_source_shortest_path_length, shortest_path_length
164 """
165 if target not in G:
166 raise nx.NodeNotFound(f"Target {target} is not in G")
167 if cutoff is None:
168 cutoff = float("inf")
169 # handle either directed or undirected
170 adj = G._pred if G.is_directed() else G._adj
171 nextlevel = [target]
172 return dict(_single_shortest_path_length(adj, nextlevel, cutoff))
175@nx._dispatchable
176def all_pairs_shortest_path_length(G, cutoff=None):
177 """Computes the shortest path lengths between all nodes in `G`.
179 Parameters
180 ----------
181 G : NetworkX graph
183 cutoff : integer, optional
184 Depth at which to stop the search. Only paths of length at most
185 `cutoff` (i.e. paths containing <= ``cutoff + 1`` nodes) are returned.
187 Returns
188 -------
189 lengths : iterator
190 (source, dictionary) iterator with dictionary keyed by target and
191 shortest path length as the key value.
193 Notes
194 -----
195 The iterator returned only has reachable node pairs.
197 Examples
198 --------
199 >>> G = nx.path_graph(5)
200 >>> length = dict(nx.all_pairs_shortest_path_length(G))
201 >>> for node in [0, 1, 2, 3, 4]:
202 ... print(f"1 - {node}: {length[1][node]}")
203 1 - 0: 1
204 1 - 1: 0
205 1 - 2: 1
206 1 - 3: 2
207 1 - 4: 3
208 >>> length[3][2]
209 1
210 >>> length[2][2]
211 0
213 Only include paths with length less than or equal to the `cutoff` keyword
214 argument:
216 >>> path_lengths = dict(nx.all_pairs_shortest_path_length(G, cutoff=2))
217 >>> path_lengths[1] # node 4 is too far away to appear
218 {1: 0, 0: 1, 2: 1, 3: 2}
219 """
220 length = single_source_shortest_path_length
221 # TODO This can be trivially parallelized.
222 for n in G:
223 yield (n, length(G, n, cutoff=cutoff))
226@nx._dispatchable
227def bidirectional_shortest_path(G, source, target):
228 """Returns a list of nodes in a shortest path between source and target.
230 Parameters
231 ----------
232 G : NetworkX graph
234 source : node label
235 starting node for path
237 target : node label
238 ending node for path
240 Returns
241 -------
242 path: list
243 List of nodes in a path from source to target.
245 Raises
246 ------
247 NetworkXNoPath
248 If no path exists between source and target.
250 Examples
251 --------
252 >>> G = nx.Graph()
253 >>> nx.add_path(G, [0, 1, 2, 3, 0, 4, 5, 6, 7, 4])
254 >>> nx.bidirectional_shortest_path(G, 2, 6)
255 [2, 1, 0, 4, 5, 6]
257 See Also
258 --------
259 shortest_path
261 Notes
262 -----
263 This algorithm is used by shortest_path(G, source, target).
264 """
266 if source not in G:
267 raise nx.NodeNotFound(f"Source {source} is not in G")
269 if target not in G:
270 raise nx.NodeNotFound(f"Target {target} is not in G")
272 # call helper to do the real work
273 results = _bidirectional_pred_succ(G, source, target)
274 pred, succ, w = results
276 # build path from pred+w+succ
277 path = []
278 # from source to w
279 while w is not None:
280 path.append(w)
281 w = pred[w]
282 path.reverse()
283 # from w to target
284 w = succ[path[-1]]
285 while w is not None:
286 path.append(w)
287 w = succ[w]
289 return path
292def _bidirectional_pred_succ(G, source, target):
293 """Bidirectional shortest path helper.
295 Returns (pred, succ, w) where
296 pred is a dictionary of predecessors from w to the source, and
297 succ is a dictionary of successors from w to the target.
298 """
299 # does BFS from both source and target and meets in the middle
300 if target == source:
301 return ({target: None}, {source: None}, source)
303 # handle either directed or undirected
304 if G.is_directed():
305 Gpred = G.pred
306 Gsucc = G.succ
307 else:
308 Gpred = G.adj
309 Gsucc = G.adj
311 # predecessor and successors in search
312 pred = {source: None}
313 succ = {target: None}
315 # initialize fringes, start with forward
316 forward_fringe = [source]
317 reverse_fringe = [target]
319 while forward_fringe and reverse_fringe:
320 if len(forward_fringe) <= len(reverse_fringe):
321 this_level = forward_fringe
322 forward_fringe = []
323 for v in this_level:
324 for w in Gsucc[v]:
325 if w not in pred:
326 forward_fringe.append(w)
327 pred[w] = v
328 if w in succ: # path found
329 return pred, succ, w
330 else:
331 this_level = reverse_fringe
332 reverse_fringe = []
333 for v in this_level:
334 for w in Gpred[v]:
335 if w not in succ:
336 succ[w] = v
337 reverse_fringe.append(w)
338 if w in pred: # found path
339 return pred, succ, w
341 raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
344@nx._dispatchable
345def single_source_shortest_path(G, source, cutoff=None):
346 """Compute shortest path between source
347 and all other nodes reachable from source.
349 Parameters
350 ----------
351 G : NetworkX graph
353 source : node label
354 Starting node for path
356 cutoff : integer, optional
357 Depth to stop the search. Only target nodes where the shortest path to
358 this node from the source node contains <= ``cutoff + 1`` nodes will be
359 included in the returned results.
361 Returns
362 -------
363 paths : dictionary
364 Dictionary, keyed by target, of shortest paths.
366 Examples
367 --------
368 >>> G = nx.path_graph(5)
369 >>> nx.single_source_shortest_path(G, 0)
370 {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3], 4: [0, 1, 2, 3, 4]}
372 Only include paths with length less than or equal to the `cutoff` keyword
373 argument:
375 >>> nx.single_source_shortest_path(G, 0, cutoff=2)
376 {0: [0], 1: [0, 1], 2: [0, 1, 2]}
378 Notes
379 -----
380 The shortest path is not necessarily unique. So there can be multiple
381 paths between the source and each target node, all of which have the
382 same 'shortest' length. For each target node, this function returns
383 only one of those paths.
385 See Also
386 --------
387 shortest_path
388 """
389 if source not in G:
390 raise nx.NodeNotFound(f"Source {source} not in G")
391 if cutoff is None:
392 cutoff = float("inf")
393 nextlevel = [source] # list of nodes to check at next level
394 paths = {source: [source]} # paths dictionary (paths to key from source)
395 return dict(_single_shortest_path(G._adj, nextlevel, paths, cutoff, operator.add))
398def _single_shortest_path(adj, firstlevel, paths, cutoff, join):
399 """Returns shortest paths
401 Shortest Path helper function
402 Parameters
403 ----------
404 adj : dict
405 Adjacency dict or view
406 firstlevel : list
407 starting nodes, e.g. [source] or [target]
408 paths : dict
409 paths for starting nodes, e.g. {source: [source]}
410 cutoff : int or float
411 level at which we stop the process
412 join : function
413 function to construct a path from two partial paths. Requires two
414 list inputs `p1` and `p2`, and returns a list. Usually returns
415 `p1 + p2` (forward from source) or `p2 + p1` (backward from target)
416 """
417 level = 0
418 nextlevel = firstlevel
419 n = len(adj)
420 while nextlevel and cutoff > level:
421 thislevel = nextlevel
422 nextlevel = []
423 for v in thislevel:
424 for w in adj[v]:
425 if w not in paths:
426 paths[w] = join(paths[v], [w])
427 nextlevel.append(w)
428 if len(paths) == n:
429 return paths
430 level += 1
431 return paths
434@nx._dispatchable
435def single_target_shortest_path(G, target, cutoff=None):
436 """Compute shortest path to target from all nodes that reach target.
438 Parameters
439 ----------
440 G : NetworkX graph
442 target : node label
443 Target node for path
445 cutoff : integer, optional
446 Depth to stop the search. Only source nodes where the shortest path
447 from this node to the target node contains <= ``cutoff + 1`` nodes will
448 be included in the returned results.
450 Returns
451 -------
452 paths : dictionary
453 Dictionary, keyed by source, of shortest paths.
455 Examples
456 --------
457 >>> G = nx.path_graph(5, create_using=nx.DiGraph())
458 >>> nx.single_target_shortest_path(G, 4)
459 {4: [4], 3: [3, 4], 2: [2, 3, 4], 1: [1, 2, 3, 4], 0: [0, 1, 2, 3, 4]}
461 Only include paths with length less than or equal to the `cutoff` keyword
462 argument:
464 >>> nx.single_target_shortest_path(G, 4, cutoff=2)
465 {4: [4], 3: [3, 4], 2: [2, 3, 4]}
467 Notes
468 -----
469 The shortest path is not necessarily unique. So there can be multiple
470 paths between the source and each target node, all of which have the
471 same 'shortest' length. For each target node, this function returns
472 only one of those paths.
474 See Also
475 --------
476 shortest_path, single_source_shortest_path
477 """
478 if target not in G:
479 raise nx.NodeNotFound(f"Target {target} not in G")
481 def join(p1, p2):
482 return p2 + p1
484 # handle undirected graphs
485 adj = G._pred if G.is_directed() else G._adj
486 if cutoff is None:
487 cutoff = float("inf")
488 nextlevel = [target] # list of nodes to check at next level
489 paths = {target: [target]} # paths dictionary (paths to key from source)
490 return dict(_single_shortest_path(adj, nextlevel, paths, cutoff, join))
493@nx._dispatchable
494def all_pairs_shortest_path(G, cutoff=None):
495 """Compute shortest paths between all nodes.
497 Parameters
498 ----------
499 G : NetworkX graph
501 cutoff : integer, optional
502 Depth at which to stop the search. Only paths containing at most
503 ``cutoff + 1`` nodes are returned.
505 Returns
506 -------
507 paths : iterator
508 Dictionary, keyed by source and target, of shortest paths.
510 Examples
511 --------
512 >>> G = nx.path_graph(5)
513 >>> path = dict(nx.all_pairs_shortest_path(G))
514 >>> print(path[0])
515 {0: [0], 1: [0, 1], 2: [0, 1, 2], 3: [0, 1, 2, 3], 4: [0, 1, 2, 3, 4]}
517 Only include paths with length less than or equal to the `cutoff` keyword
518 argument:
520 >>> path = dict(nx.all_pairs_shortest_path(G, cutoff=2))
521 >>> print(path[0])
522 {0: [0], 1: [0, 1], 2: [0, 1, 2]}
524 Notes
525 -----
526 There may be multiple shortest paths with the same length between
527 two nodes. For each pair, this function returns only one of those paths.
529 See Also
530 --------
531 floyd_warshall
532 all_pairs_all_shortest_paths
534 """
535 # TODO This can be trivially parallelized.
536 for n in G:
537 yield (n, single_source_shortest_path(G, n, cutoff=cutoff))
540@nx._dispatchable
541def predecessor(G, source, target=None, cutoff=None, return_seen=None):
542 """Returns dict of predecessors for the path from source to all nodes in G.
544 Parameters
545 ----------
546 G : NetworkX graph
548 source : node label
549 Starting node for path
551 target : node label, optional
552 Ending node for path. If provided only predecessors between
553 source and target are returned
555 cutoff : integer, optional
556 Depth to stop the search. Only paths of length <= `cutoff` are
557 returned.
559 return_seen : bool, optional (default=None)
560 Whether to return a dictionary, keyed by node, of the level (number of
561 hops) to reach the node (as seen during breadth-first-search).
563 Returns
564 -------
565 pred : dictionary
566 Dictionary, keyed by node, of predecessors in the shortest path.
569 (pred, seen): tuple of dictionaries
570 If `return_seen` argument is set to `True`, then a tuple of dictionaries
571 is returned. The first element is the dictionary, keyed by node, of
572 predecessors in the shortest path. The second element is the dictionary,
573 keyed by node, of the level (number of hops) to reach the node (as seen
574 during breadth-first-search).
576 Examples
577 --------
578 >>> G = nx.path_graph(4)
579 >>> list(G)
580 [0, 1, 2, 3]
581 >>> nx.predecessor(G, 0)
582 {0: [], 1: [0], 2: [1], 3: [2]}
583 >>> nx.predecessor(G, 0, cutoff=2)
584 {0: [], 1: [0], 2: [1]}
585 >>> nx.predecessor(G, 0, return_seen=True)
586 ({0: [], 1: [0], 2: [1], 3: [2]}, {0: 0, 1: 1, 2: 2, 3: 3})
589 """
590 if source not in G:
591 raise nx.NodeNotFound(f"Source {source} not in G")
593 level = 0 # the current level
594 nextlevel = [source] # list of nodes to check at next level
595 seen = {source: level} # level (number of hops) when seen in BFS
596 pred = {source: []} # predecessor dictionary
597 while nextlevel:
598 level = level + 1
599 thislevel = nextlevel
600 nextlevel = []
601 for v in thislevel:
602 for w in G[v]:
603 if w not in seen:
604 pred[w] = [v]
605 seen[w] = level
606 nextlevel.append(w)
607 elif seen[w] == level: # add v to predecessor list if it
608 pred[w].append(v) # is at the correct level
609 if cutoff and cutoff <= level:
610 break
612 if target is not None:
613 if return_seen:
614 if target not in pred:
615 return ([], -1) # No predecessor
616 return (pred[target], seen[target])
617 else:
618 if target not in pred:
619 return [] # No predecessor
620 return pred[target]
621 else:
622 if return_seen:
623 return (pred, seen)
624 else:
625 return pred