1
2 """
3 Shortest path algorithms.
4 """
5 __author__ = """Aric Hagberg (hagberg@lanl.gov)"""
6 ___revision__ = ""
7
8
9
10
11
12
13 import networkx
14
15
16 import heapq
17
18
20 """Return the shortest path length in the graph G between
21 the source and target. Raise an exception if no path exists.
22
23 G is treated as an unweighted graph. For weighted graphs
24 see dijkstra_path_length.
25 """
26 path=bidirectional_shortest_path(G,source,target)
27 if path is False:
28 raise networkx.NetworkXError,\
29 "no path from %s to %s"%(source,target)
30 return len(path)-1
31
33 """
34 Shortest path length from source to all reachable nodes.
35
36 Returns a dictionary of shortest path lengths keyed by target.
37
38 >>> G=path_graph(5)
39 >>> length=single_source_shortest_path_length(G,1)
40 >>> length[4]
41 3
42 >>> print length
43 {0: 1, 1: 0, 2: 1, 3: 2, 4: 3}
44
45 cutoff is optional integer depth to stop the search - only
46 paths of length <= cutoff are returned.
47
48 """
49 seen={}
50 level=0
51 nextlevel={source:1}
52 while nextlevel:
53 thislevel=nextlevel
54 nextlevel={}
55 for v in thislevel:
56 if not seen.has_key(v):
57 seen[v]=level
58 nbrs=dict.fromkeys(G.neighbors_iter(v),1)
59 nextlevel.update(nbrs)
60 if (cutoff is not None and cutoff <= level): break
61 level=level+1
62 return seen
63
64
66 """ Return dictionary of shortest path lengths between all nodes in G.
67
68 The dictionary only has keys for reachable node pairs.
69 >>> G=path_graph(5)
70 >>> length=all_pairs_shortest_path_length(G)
71 >>> print length[1][4]
72 3
73 >>> length[1]
74 {0: 1, 1: 0, 2: 1, 3: 2, 4: 3}
75
76
77 cutoff is optional integer depth to stop the search - only
78 paths of length <= cutoff are returned.
79
80 """
81 paths={}
82 for n in G:
83 paths[n]=single_source_shortest_path_length(G,n,cutoff=cutoff)
84 return paths
85
87 """Return a list of nodes in G for a shortest path between source
88 and target.
89
90 There may be more than one shortest path. This returns only one.
91
92 """
93 return bidirectional_shortest_path(G,source,target)
94
95
97 """
98 Return list of nodes in a shortest path between source and target.
99 Return False if no path exists.
100
101 Also known as shortest_path.
102
103 """
104
105 results=_bidirectional_pred_succ(G,source,target)
106 if results is False:
107 return False
108 pred,succ,w=results
109
110
111 path=[]
112
113 while w is not None:
114 path.append(w)
115 w=succ[w]
116
117 w=pred[path[0]]
118 while w is not None:
119 path.insert(0,w)
120 w=pred[w]
121
122 return path
123
125 """
126 Bidirectional shortest path helper.
127
128 Returns (pred,succ,w) where
129 pred is a dictionary of predecessors from w to the source, and
130 succ is a dictionary of successors from w to the target.
131 """
132
133 if source is None or target is None:
134 raise NetworkXException(\
135 "Bidirectional shortest path called without source or target")
136 if target == source: return ({1:None},{1:None},1)
137
138
139 if G.is_directed():
140 Gpred=G.predecessors_iter
141 Gsucc=G.successors_iter
142 else:
143 Gpred=G.neighbors_iter
144 Gsucc=G.neighbors_iter
145
146
147 pred={source:None}
148 succ={target:None}
149
150
151 forward_fringe=[source]
152 reverse_fringe=[target]
153
154 while forward_fringe and reverse_fringe:
155 this_level=forward_fringe
156 forward_fringe=[]
157 for v in this_level:
158 for w in Gsucc(v):
159 if w not in pred:
160 forward_fringe.append(w)
161 pred[w]=v
162 if w in succ: return pred,succ,w
163 this_level=reverse_fringe
164 reverse_fringe=[]
165 for v in this_level:
166 for w in Gpred(v):
167 if w not in succ:
168 succ[w]=v
169 reverse_fringe.append(w)
170 if w in pred: return pred,succ,w
171
172 return False
173
174
176 """
177 Return list of nodes in a shortest path between source
178 and all other nodes in G reachable from source.
179
180 There may be more than one shortest path between the
181 source and target nodes - this routine returns only one.
182
183 cutoff is optional integer depth to stop the search - only
184 paths of length <= cutoff are returned.
185
186 See also shortest_path and bidirectional_shortest_path.
187 """
188 level=0
189 nextlevel={source:1}
190 paths={source:[source]}
191 if cutoff==0:
192 return paths
193 while nextlevel:
194 thislevel=nextlevel
195 nextlevel={}
196 for v in thislevel:
197 for w in G.neighbors(v):
198 if not paths.has_key(w):
199 paths[w]=paths[v]+[w]
200 nextlevel[w]=1
201 level=level+1
202 if (cutoff is not None and cutoff <= level): break
203 return paths
204
205
207 """ Return dictionary of shortest paths between all nodes in G.
208
209 The dictionary only has keys for reachable node pairs.
210
211 cutoff is optional integer depth to stop the search - only
212 paths of length <= cutoff are returned.
213
214 See also floyd_warshall.
215
216 """
217 paths={}
218 for n in G:
219 paths[n]=single_source_shortest_path(G,n,cutoff=cutoff)
220 return paths
221
222
224 """
225 Returns the shortest path from source to target in a weighted
226 graph G. Uses a bidirectional version of Dijkstra's algorithm.
227
228 Edge data must be numerical values for XGraph and XDiGraphs.
229 The weights are assigned to be 1 for Graphs and DiGraphs.
230
231 See also bidirectional_dijkstra for more information about the algorithm.
232 """
233
234
235 (length,path)=single_source_dijkstra(G,source)
236 try:
237 return path[target]
238 except KeyError:
239 raise networkx.NetworkXError, \
240 "node %s not reachable from %s"%(source,target)
241
242
244 """
245 Returns the shortest path length from source to target in a weighted
246 graph G. Uses a bidirectional version of Dijkstra's algorithm.
247
248 Edge data must be numerical values for XGraph and XDiGraphs.
249 The weights are assigned to be 1 for Graphs and DiGraphs.
250
251 See also bidirectional_dijkstra for more information about the algorithm.
252
253 """
254
255
256
257 (length,path)=single_source_dijkstra(G,source)
258 try:
259 return length[target]
260 except KeyError:
261 raise networkx.NetworkXError, \
262 "node %s not reachable from %s"%(source,target)
263
264
265
267 """
268 Dijkstra's algorithm for shortest paths using bidirectional search.
269
270 Returns a two-tuple (d,p) where d is the distance and p
271 is the path from the source to the target.
272
273 Distances are calculated as sums of weighted edges traversed.
274
275 Edges must hold numerical values for XGraph and XDiGraphs.
276 The weights are set to 1 for Graphs and DiGraphs.
277
278 In practice bidirectional Dijkstra is much more than twice as fast as
279 ordinary Dijkstra.
280
281 Ordinary Dijkstra expands nodes in a sphere-like manner from the
282 source. The radius of this sphere will eventually be the length
283 of the shortest path. Bidirectional Dijkstra will expand nodes
284 from both the source and the target, making two spheres of half
285 this radius. Volume of the first sphere is pi*r*r while the
286 others are 2*pi*r/2*r/2, making up half the volume.
287
288 This algorithm is not guaranteed to work if edge weights
289 are negative or are floating point numbers
290 (overflows and roundoff errors can cause problems).
291
292 """
293 if source is None or target is None:
294 raise NetworkXException(
295 "Bidirectional Dijkstra called with no source or target")
296 if source == target: return (0, [source])
297
298 dists = [{}, {}]
299 paths = [{source:[source]}, {target:[target]}]
300 fringe = [[], []]
301 seen = [{source:0}, {target:0} ]
302
303 heapq.heappush(fringe[0], (0, source))
304 heapq.heappush(fringe[1], (0, target))
305
306 if G.is_directed():
307 neighs = [G.successors_iter, G.predecessors_iter]
308 else:
309 neighs = [G.neighbors_iter, G.neighbors_iter]
310
311
312 finalpath = []
313
314
315 if not hasattr(G,"get_edge"): G.get_edge=lambda x,y:1
316 dir = 1
317 while fringe[0] and fringe[1]:
318
319
320 dir = 1-dir
321
322 (dist, v )= heapq.heappop(fringe[dir])
323 if v in dists[dir]:
324
325 continue
326
327 dists[dir][v] = dist
328 if v in dists[1-dir]:
329
330
331 return (finaldist,finalpath)
332 for w in neighs[dir](v):
333 if(dir==0):
334 vwLength = dists[dir][v] + G.get_edge(v,w)
335 else:
336 vwLength = dists[dir][v] + G.get_edge(w,v)
337
338 if w in dists[dir]:
339 if vwLength < dists[dir][w]:
340 raise ValueError,\
341 "Contradictory paths found: negative weights?"
342 elif w not in seen[dir] or vwLength < seen[dir][w]:
343
344 seen[dir][w] = vwLength
345 heapq.heappush(fringe[dir], (vwLength,w))
346 paths[dir][w] = paths[dir][v]+[w]
347 if w in seen[0] and w in seen[1]:
348
349
350 totaldist = seen[0][w] + seen[1][w]
351 if finalpath == [] or finaldist > totaldist:
352 finaldist = totaldist
353 revpath = paths[1][w][:]
354 revpath.reverse()
355 finalpath = paths[0][w] + revpath[1:]
356 return False
357
358
359
360
361
362
364 """
365 Returns the shortest paths from source to all other reachable
366 nodes in a weighted graph G. Uses Dijkstra's algorithm.
367
368 Returns a dictionary of shortest path lengths keyed by source.
369
370 Edge data must be numerical values for XGraph and XDiGraphs.
371 The weights are assigned to be 1 for Graphs and DiGraphs.
372
373 See also single_source_dijkstra for more information about the algorithm.
374
375 """
376 (length,path)=single_source_dijkstra(G,source)
377 return path
378
379
381 """
382 Returns the shortest path lengths from source to all other
383 reachable nodes in a weighted graph G. Uses Dijkstra's algorithm.
384
385 Returns a dictionary of shortest path lengths keyed by source.
386
387 Edge data must be numerical values for XGraph and XDiGraphs.
388 The weights are assigned to be 1 for Graphs and DiGraphs.
389
390 See also single_source_dijkstra for more information about the algorithm.
391
392 """
393 (length,path)=single_source_dijkstra(G,source)
394 return length
395
396
398 """
399 Dijkstra's algorithm for shortest paths in a weighted graph G.
400
401 Use:
402
403 single_source_dijkstra_path() - shortest path list of nodes
404
405 single_source_dijkstra_path_length() - shortest path length
406
407 Returns a tuple of two dictionaries keyed by node.
408 The first stores distance from the source.
409 The second stores the path from the source to that node.
410
411 Distances are calculated as sums of weighted edges traversed.
412 Edges must hold numerical values for XGraph and XDiGraphs.
413 The weights are 1 for Graphs and DiGraphs.
414
415 Optional target argument stops the search when target is found.
416
417 Based on the Python cookbook recipe (119466) at
418 http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466
419
420 This algorithm is not guaranteed to work if edge weights
421 are negative or are floating point numbers
422 (overflows and roundoff errors can cause problems).
423
424 See also 'bidirectional_dijkstra_path'
425 """
426 if source==target: return (0, [source])
427 dist = {}
428 paths = {source:[source]}
429 seen = {source:0}
430 fringe=[]
431 heapq.heappush(fringe,(0,source))
432 while fringe:
433 (d,v)=heapq.heappop(fringe)
434 if v in dist: continue
435 dist[v] = seen[v]
436 if v == target: break
437 for w in G.neighbors(v):
438 vw_dist = dist[v] + G.get_edge(v,w)
439 if w in dist:
440 if vw_dist < dist[w]:
441 raise ValueError,\
442 "Contradictory paths found: negative weights?"
443 elif w not in seen or vw_dist < seen[w]:
444 seen[w] = vw_dist
445 heapq.heappush(fringe,(vw_dist,w))
446 paths[w] = paths[v]+[w]
447 return (dist,paths)
448
450 """
451 Same algorithm as for single_source_dijsktra, but returns two
452 dicts representing a list of predecessors of a node and the
453 distance to each node respectively. The list of predecessors
454 contains more than one element only when there are more than one
455 shortest paths to the key node.
456
457 This routine is intended for use with the betweenness centrality
458 algorithms in centrality.py.
459 """
460 push=heapq.heappush
461 pop=heapq.heappop
462 dist = {}
463 pred = {source:[]}
464 seen = {source:0}
465 fringe=[]
466 push(fringe,(0,source))
467 while fringe:
468 (d,v)=pop(fringe)
469 if v in dist: continue
470 dist[v] = seen[v]
471 for w in G.neighbors(v):
472 vw_dist = dist[v] + G.get_edge(v,w)
473 if w in dist:
474 if vw_dist < dist[w]:
475 raise ValueError,\
476 "Contradictory paths found: negative weights?"
477 elif w not in seen or vw_dist < seen[w]:
478 seen[w] = vw_dist
479 push(fringe,(vw_dist,w))
480 pred[w] = [v]
481 elif vw_dist==seen[w]:
482 pred[w].append(v)
483 return (pred,dist)
484
485
486
487
489 """
490 The Floyd-Warshall algorithm for all pairs shortest paths.
491
492 Returns a tuple (distance,path) containing two arrays of shortest
493 distance and paths as a predecessor matrix.
494
495 This differs from
496 floyd_warshall only in the types of the return values. Thus,
497 path[i,j] gives the predecessor at j on a path from i to j. A
498 value of None indicates that no path exists. A predecessor of i
499 indicates the beginning of the path. The advantage of this
500 implementation is that, while running time is O(n^3), running
501 space is O(n^2).
502
503 This algorithm handles negative weights.
504 """
505
506
507 HUGE_VAL = 1
508 for e in graph.edges():
509 HUGE_VAL += abs(graph.get_edge(e[0],e[1]))
510
511 dist = {}
512 dist_prev = {}
513 pred = {}
514 pred_prev = {}
515 for i in graph:
516 dist[i] = {}
517 dist_prev[i] = {}
518 pred[i] = {}
519 pred_prev[i] = {}
520 for j in graph:
521 dist[i][j] = 0
522 pred[i][j] = 0
523 if i == j:
524 dist_prev[i][j] = 0
525 pred_prev[i][j] = -1
526 elif graph.has_edge(i,j):
527 val = graph.get_edge(i,j)
528 dist_prev[i][j] = val
529 pred_prev[i][j] = i
530 else:
531
532 dist_prev[i][j] = HUGE_VAL
533 pred_prev[i][j] = -1
534 for k in graph:
535 for i in graph:
536 for j in graph:
537 dist[i][j] = min(dist_prev[i][j], dist_prev[i][k] + dist_prev[k][j])
538 if dist_prev[i][j] <= dist_prev[i][k] + dist[k][j]:
539 pred[i][j] = pred_prev[i][j]
540 else:
541 pred[i][j] = pred_prev[k][j]
542 tmp = dist_prev
543 dist_prev = dist
544 dist = tmp
545
546 tmp = pred_prev
547 pred_prev = pred
548 pred = tmp
549
550
551
552 return dist_prev, pred_prev
553
554
556 """
557 The Floyd-Warshall algorithm for all pairs shortest paths.
558
559 Returns a tuple (distance,path) containing two dictionaries of shortest
560 distance and predecessor paths.
561
562 This algorithm is most appropriate for dense graphs.
563 The running time is O(n^3), and running space is O(n^2)
564 where n is the number of nodes in G.
565
566 For sparse graphs, see
567
568 all_pairs_shortest_path
569 all_pairs_shortest_path_length
570
571 which are based on Dijkstra's algorithm.
572
573 """
574
575 dist={}
576
577
578
579 pred={}
580
581 for u in G.nodes():
582 dist[u]={}
583 pred[u]={}
584 for v in G.nodes():
585 if G.has_edge(u,v):
586 dist[u][v]=G.get_edge(u,v)
587 pred[u][v]=u
588 else:
589 dist[u][v]=huge
590 pred[u][v]=None
591 dist[u][u]=0
592
593 for w in G.nodes():
594 for u in G.nodes():
595 for v in G.nodes():
596 if dist[u][v] > dist[u][w] + dist[w][v]:
597 dist[u][v] = dist[u][w] + dist[w][v]
598 pred[u][v] = pred[w][v]
599 return dist,pred
600
601
602 -def predecessor(G,source,target=None,cutoff=None,return_seen=None):
603 """ Returns dictionary of predecessors for the path from source to all
604 nodes in G.
605
606 Optional target returns only predecessors between source and target.
607 Cutoff is a limit on the number of hops traversed.
608
609 Example for the path graph 0-1-2-3
610
611 >>> G=path_graph(4)
612 >>> print G.nodes()
613 [0, 1, 2, 3]
614 >>> predecessor(G,0)
615 {0: [], 1: [0], 2: [1], 3: [2]}
616
617 """
618 level=0
619 nextlevel=[source]
620 seen={source:level}
621 pred={source:[]}
622 while nextlevel:
623 level=level+1
624 thislevel=nextlevel
625 nextlevel=[]
626 for v in thislevel:
627 for w in G.neighbors(v):
628 if (not seen.has_key(w)):
629 pred[w]=[v]
630 seen[w]=level
631 nextlevel.append(w)
632 elif (seen[w]==level):
633 pred[w].append(v)
634 if (cutoff and cutoff <= level):
635 break
636
637 if target is not None:
638 if return_seen:
639 if not pred.has_key(target): return ([],-1)
640 return (pred[target],seen[target])
641 else:
642 if not pred.has_key(target): return []
643 return pred[target]
644 else:
645 if return_seen:
646 return (pred,seen)
647 else:
648 return pred
649
650
652 import doctest
653 suite = doctest.DocFileSuite('tests/shortest_path.txt',package='networkx')
654 return suite
655
656
657 if __name__ == "__main__":
658 import os
659 import sys
660 import unittest
661 if sys.version_info[:2] < (2, 4):
662 print "Python version 2.4 or later required for tests (%d.%d detected)." % sys.version_info[:2]
663 sys.exit(-1)
664
665 nxbase=sys.path[0]+os.sep+os.pardir
666 sys.path.insert(0,nxbase)
667 unittest.TextTestRunner().run(_test_suite())
668