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 networkx as nx
7__all__ = [
8 "bidirectional_shortest_path",
9 "single_source_shortest_path",
10 "single_source_shortest_path_length",
11 "single_target_shortest_path",
12 "single_target_shortest_path_length",
13 "all_pairs_shortest_path",
14 "all_pairs_shortest_path_length",
15 "predecessor",
16]
19@nx._dispatchable
20def single_source_shortest_path_length(G, source, cutoff=None):
21 """Compute the shortest path lengths from `source` to all reachable nodes in `G`.
23 Parameters
24 ----------
25 G : NetworkX graph
27 source : node
28 Starting node for path
30 cutoff : integer, optional
31 Depth to stop the search. Only paths of length <= `cutoff` are returned.
33 Returns
34 -------
35 lengths : dict
36 Dict keyed by node to shortest path length to `source`.
38 Examples
39 --------
40 >>> G = nx.path_graph(5)
41 >>> nx.single_source_shortest_path_length(G, 0)
42 {0: 0, 1: 1, 2: 2, 3: 3, 4: 4}
44 See Also
45 --------
46 :any:`shortest_path_length` :
47 Shortest path length with specifiable source, target, and weight.
48 :any:`single_source_dijkstra_path_length` :
49 Shortest weighted path length from source with Dijkstra algorithm.
50 :any:`single_source_bellman_ford_path_length` :
51 Shortest weighted path length from source with Bellman-Ford algorithm.
52 """
53 if source not in G:
54 raise nx.NodeNotFound(f"Source {source} is not in G")
55 if cutoff is None:
56 cutoff = float("inf")
57 nextlevel = [source]
58 return dict(_single_shortest_path_length(G._adj, nextlevel, cutoff))
61def _single_shortest_path_length(adj, firstlevel, cutoff):
62 """Yields (node, level) in a breadth first search
64 Shortest Path Length helper function
65 Parameters
66 ----------
67 adj : dict
68 Adjacency dict or view
69 firstlevel : list
70 starting nodes, e.g. [source] or [target]
71 cutoff : int or float
72 level at which we stop the process
73 """
74 seen = set(firstlevel)
75 nextlevel = firstlevel
76 level = 0
77 n = len(adj)
78 for v in nextlevel:
79 yield (v, level)
80 while nextlevel and cutoff > level:
81 level += 1
82 thislevel = nextlevel
83 nextlevel = []
84 for v in thislevel:
85 for w in adj[v]:
86 if w not in seen:
87 seen.add(w)
88 nextlevel.append(w)
89 yield (w, level)
90 if len(seen) == n:
91 return
94@nx._dispatchable
95def single_target_shortest_path_length(G, target, cutoff=None):
96 """Compute the shortest path lengths to target from all reachable nodes.
98 Parameters
99 ----------
100 G : NetworkX graph
102 target : node
103 Target node for path
105 cutoff : integer, optional
106 Depth to stop the search. Only paths of length <= cutoff are returned.
108 Returns
109 -------
110 lengths : dictionary
111 Dictionary, keyed by source, of shortest path lengths.
113 Examples
114 --------
115 >>> G = nx.path_graph(5, create_using=nx.DiGraph())
116 >>> length = nx.single_target_shortest_path_length(G, 4)
117 >>> length[0]
118 4
119 >>> for node in range(5):
120 ... print(f"{node}: {length[node]}")
121 0: 4
122 1: 3
123 2: 2
124 3: 1
125 4: 0
127 See Also
128 --------
129 single_source_shortest_path_length, shortest_path_length
130 """
131 if target not in G:
132 raise nx.NodeNotFound(f"Target {target} is not in G")
133 if cutoff is None:
134 cutoff = float("inf")
135 # handle either directed or undirected
136 adj = G._pred if G.is_directed() else G._adj
137 nextlevel = [target]
138 return dict(_single_shortest_path_length(adj, nextlevel, cutoff))
141@nx._dispatchable
142def all_pairs_shortest_path_length(G, cutoff=None):
143 """Computes the shortest path lengths between all nodes in `G`.
145 Parameters
146 ----------
147 G : NetworkX graph
149 cutoff : integer, optional
150 Depth at which to stop the search. Only paths of length at most
151 `cutoff` are returned.
153 Returns
154 -------
155 lengths : iterator
156 (source, dictionary) iterator with dictionary keyed by target and
157 shortest path length as the key value.
159 Notes
160 -----
161 The iterator returned only has reachable node pairs.
163 Examples
164 --------
165 >>> G = nx.path_graph(5)
166 >>> length = dict(nx.all_pairs_shortest_path_length(G))
167 >>> for node in [0, 1, 2, 3, 4]:
168 ... print(f"1 - {node}: {length[1][node]}")
169 1 - 0: 1
170 1 - 1: 0
171 1 - 2: 1
172 1 - 3: 2
173 1 - 4: 3
174 >>> length[3][2]
175 1
176 >>> length[2][2]
177 0
179 """
180 length = single_source_shortest_path_length
181 # TODO This can be trivially parallelized.
182 for n in G:
183 yield (n, length(G, n, cutoff=cutoff))
186@nx._dispatchable
187def bidirectional_shortest_path(G, source, target):
188 """Returns a list of nodes in a shortest path between source and target.
190 Parameters
191 ----------
192 G : NetworkX graph
194 source : node label
195 starting node for path
197 target : node label
198 ending node for path
200 Returns
201 -------
202 path: list
203 List of nodes in a path from source to target.
205 Raises
206 ------
207 NetworkXNoPath
208 If no path exists between source and target.
210 Examples
211 --------
212 >>> G = nx.Graph()
213 >>> nx.add_path(G, [0, 1, 2, 3, 0, 4, 5, 6, 7, 4])
214 >>> nx.bidirectional_shortest_path(G, 2, 6)
215 [2, 1, 0, 4, 5, 6]
217 See Also
218 --------
219 shortest_path
221 Notes
222 -----
223 This algorithm is used by shortest_path(G, source, target).
224 """
226 if source not in G:
227 raise nx.NodeNotFound(f"Source {source} is not in G")
229 if target not in G:
230 raise nx.NodeNotFound(f"Target {target} is not in G")
232 # call helper to do the real work
233 results = _bidirectional_pred_succ(G, source, target)
234 pred, succ, w = results
236 # build path from pred+w+succ
237 path = []
238 # from source to w
239 while w is not None:
240 path.append(w)
241 w = pred[w]
242 path.reverse()
243 # from w to target
244 w = succ[path[-1]]
245 while w is not None:
246 path.append(w)
247 w = succ[w]
249 return path
252def _bidirectional_pred_succ(G, source, target):
253 """Bidirectional shortest path helper.
255 Returns (pred, succ, w) where
256 pred is a dictionary of predecessors from w to the source, and
257 succ is a dictionary of successors from w to the target.
258 """
259 # does BFS from both source and target and meets in the middle
260 if target == source:
261 return ({target: None}, {source: None}, source)
263 # handle either directed or undirected
264 if G.is_directed():
265 Gpred = G.pred
266 Gsucc = G.succ
267 else:
268 Gpred = G.adj
269 Gsucc = G.adj
271 # predecessor and successors in search
272 pred = {source: None}
273 succ = {target: None}
275 # initialize fringes, start with forward
276 forward_fringe = [source]
277 reverse_fringe = [target]
279 while forward_fringe and reverse_fringe:
280 if len(forward_fringe) <= len(reverse_fringe):
281 this_level = forward_fringe
282 forward_fringe = []
283 for v in this_level:
284 for w in Gsucc[v]:
285 if w not in pred:
286 forward_fringe.append(w)
287 pred[w] = v
288 if w in succ: # path found
289 return pred, succ, w
290 else:
291 this_level = reverse_fringe
292 reverse_fringe = []
293 for v in this_level:
294 for w in Gpred[v]:
295 if w not in succ:
296 succ[w] = v
297 reverse_fringe.append(w)
298 if w in pred: # found path
299 return pred, succ, w
301 raise nx.NetworkXNoPath(f"No path between {source} and {target}.")
304@nx._dispatchable
305def single_source_shortest_path(G, source, cutoff=None):
306 """Compute shortest path between source
307 and all other nodes reachable from source.
309 Parameters
310 ----------
311 G : NetworkX graph
313 source : node label
314 Starting node for path
316 cutoff : integer, optional
317 Depth to stop the search. Only paths of length <= cutoff are returned.
319 Returns
320 -------
321 paths : dictionary
322 Dictionary, keyed by target, of shortest paths.
324 Examples
325 --------
326 >>> G = nx.path_graph(5)
327 >>> path = nx.single_source_shortest_path(G, 0)
328 >>> path[4]
329 [0, 1, 2, 3, 4]
331 Notes
332 -----
333 The shortest path is not necessarily unique. So there can be multiple
334 paths between the source and each target node, all of which have the
335 same 'shortest' length. For each target node, this function returns
336 only one of those paths.
338 See Also
339 --------
340 shortest_path
341 """
342 if source not in G:
343 raise nx.NodeNotFound(f"Source {source} not in G")
345 def join(p1, p2):
346 return p1 + p2
348 if cutoff is None:
349 cutoff = float("inf")
350 nextlevel = {source: 1} # list of nodes to check at next level
351 paths = {source: [source]} # paths dictionary (paths to key from source)
352 return dict(_single_shortest_path(G.adj, nextlevel, paths, cutoff, join))
355def _single_shortest_path(adj, firstlevel, paths, cutoff, join):
356 """Returns shortest paths
358 Shortest Path helper function
359 Parameters
360 ----------
361 adj : dict
362 Adjacency dict or view
363 firstlevel : dict
364 starting nodes, e.g. {source: 1} or {target: 1}
365 paths : dict
366 paths for starting nodes, e.g. {source: [source]}
367 cutoff : int or float
368 level at which we stop the process
369 join : function
370 function to construct a path from two partial paths. Requires two
371 list inputs `p1` and `p2`, and returns a list. Usually returns
372 `p1 + p2` (forward from source) or `p2 + p1` (backward from target)
373 """
374 level = 0 # the current level
375 nextlevel = firstlevel
376 while nextlevel and cutoff > level:
377 thislevel = nextlevel
378 nextlevel = {}
379 for v in thislevel:
380 for w in adj[v]:
381 if w not in paths:
382 paths[w] = join(paths[v], [w])
383 nextlevel[w] = 1
384 level += 1
385 return paths
388@nx._dispatchable
389def single_target_shortest_path(G, target, cutoff=None):
390 """Compute shortest path to target from all nodes that reach target.
392 Parameters
393 ----------
394 G : NetworkX graph
396 target : node label
397 Target node for path
399 cutoff : integer, optional
400 Depth to stop the search. Only paths of length <= cutoff are returned.
402 Returns
403 -------
404 paths : dictionary
405 Dictionary, keyed by target, of shortest paths.
407 Examples
408 --------
409 >>> G = nx.path_graph(5, create_using=nx.DiGraph())
410 >>> path = nx.single_target_shortest_path(G, 4)
411 >>> path[0]
412 [0, 1, 2, 3, 4]
414 Notes
415 -----
416 The shortest path is not necessarily unique. So there can be multiple
417 paths between the source and each target node, all of which have the
418 same 'shortest' length. For each target node, this function returns
419 only one of those paths.
421 See Also
422 --------
423 shortest_path, single_source_shortest_path
424 """
425 if target not in G:
426 raise nx.NodeNotFound(f"Target {target} not in G")
428 def join(p1, p2):
429 return p2 + p1
431 # handle undirected graphs
432 adj = G.pred if G.is_directed() else G.adj
433 if cutoff is None:
434 cutoff = float("inf")
435 nextlevel = {target: 1} # list of nodes to check at next level
436 paths = {target: [target]} # paths dictionary (paths to key from source)
437 return dict(_single_shortest_path(adj, nextlevel, paths, cutoff, join))
440@nx._dispatchable
441def all_pairs_shortest_path(G, cutoff=None):
442 """Compute shortest paths between all nodes.
444 Parameters
445 ----------
446 G : NetworkX graph
448 cutoff : integer, optional
449 Depth at which to stop the search. Only paths of length at most
450 `cutoff` are returned.
452 Returns
453 -------
454 paths : iterator
455 Dictionary, keyed by source and target, of shortest paths.
457 Examples
458 --------
459 >>> G = nx.path_graph(5)
460 >>> path = dict(nx.all_pairs_shortest_path(G))
461 >>> print(path[0][4])
462 [0, 1, 2, 3, 4]
464 Notes
465 -----
466 There may be multiple shortest paths with the same length between
467 two nodes. For each pair, this function returns only one of those paths.
469 See Also
470 --------
471 floyd_warshall
472 all_pairs_all_shortest_paths
474 """
475 # TODO This can be trivially parallelized.
476 for n in G:
477 yield (n, single_source_shortest_path(G, n, cutoff=cutoff))
480@nx._dispatchable
481def predecessor(G, source, target=None, cutoff=None, return_seen=None):
482 """Returns dict of predecessors for the path from source to all nodes in G.
484 Parameters
485 ----------
486 G : NetworkX graph
488 source : node label
489 Starting node for path
491 target : node label, optional
492 Ending node for path. If provided only predecessors between
493 source and target are returned
495 cutoff : integer, optional
496 Depth to stop the search. Only paths of length <= cutoff are returned.
498 return_seen : bool, optional (default=None)
499 Whether to return a dictionary, keyed by node, of the level (number of
500 hops) to reach the node (as seen during breadth-first-search).
502 Returns
503 -------
504 pred : dictionary
505 Dictionary, keyed by node, of predecessors in the shortest path.
508 (pred, seen): tuple of dictionaries
509 If `return_seen` argument is set to `True`, then a tuple of dictionaries
510 is returned. The first element is the dictionary, keyed by node, of
511 predecessors in the shortest path. The second element is the dictionary,
512 keyed by node, of the level (number of hops) to reach the node (as seen
513 during breadth-first-search).
515 Examples
516 --------
517 >>> G = nx.path_graph(4)
518 >>> list(G)
519 [0, 1, 2, 3]
520 >>> nx.predecessor(G, 0)
521 {0: [], 1: [0], 2: [1], 3: [2]}
522 >>> nx.predecessor(G, 0, return_seen=True)
523 ({0: [], 1: [0], 2: [1], 3: [2]}, {0: 0, 1: 1, 2: 2, 3: 3})
526 """
527 if source not in G:
528 raise nx.NodeNotFound(f"Source {source} not in G")
530 level = 0 # the current level
531 nextlevel = [source] # list of nodes to check at next level
532 seen = {source: level} # level (number of hops) when seen in BFS
533 pred = {source: []} # predecessor dictionary
534 while nextlevel:
535 level = level + 1
536 thislevel = nextlevel
537 nextlevel = []
538 for v in thislevel:
539 for w in G[v]:
540 if w not in seen:
541 pred[w] = [v]
542 seen[w] = level
543 nextlevel.append(w)
544 elif seen[w] == level: # add v to predecessor list if it
545 pred[w].append(v) # is at the correct level
546 if cutoff and cutoff <= level:
547 break
549 if target is not None:
550 if return_seen:
551 if target not in pred:
552 return ([], -1) # No predecessor
553 return (pred[target], seen[target])
554 else:
555 if target not in pred:
556 return [] # No predecessor
557 return pred[target]
558 else:
559 if return_seen:
560 return (pred, seen)
561 else:
562 return pred