1
# -*- coding: utf-8 -*-
3
Shortest path algorithms.
5
__author__ = """Aric Hagberg (hagberg@lanl.gov)"""
7
# Copyright (C) 2004-2006 by
8
# Aric Hagberg <hagberg@lanl.gov>
9
# Dan Schult <dschult@colgate.edu>
10
# Pieter Swart <swart@lanl.gov>
11
# Distributed under the terms of the GNU Lesser General Public License
12
# http://www.gnu.org/copyleft/lesser.html
14
#use deque only if networkx requires python 2.4
15
#from collections import deque
19
def shortest_path_length(G,source,target):
20
"""Return the shortest path length in the graph G between
21
the source and target. Raise an exception if no path exists.
23
G is treated as an unweighted graph. For weighted graphs
24
see dijkstra_path_length.
26
path=bidirectional_shortest_path(G,source,target)
28
raise networkx.NetworkXError,\
29
"no path from %s to %s"%(source,target)
32
def single_source_shortest_path_length(G,source,cutoff=None):
34
Shortest path length from source to all reachable nodes.
36
Returns a dictionary of shortest path lengths keyed by target.
39
>>> length=single_source_shortest_path_length(G,1)
43
{0: 1, 1: 0, 2: 1, 3: 2, 4: 3}
45
cutoff is optional integer depth to stop the search - only
46
paths of length <= cutoff are returned.
49
seen={} # level (number of hops) when seen in BFS
50
level=0 # the current level
51
nextlevel={source:1} # dict of nodes to check at next level
53
thislevel=nextlevel # advance to next level
54
nextlevel={} # and start a new list (fringe)
56
if not seen.has_key(v):
57
seen[v]=level # set the level of vertex v
58
nbrs=dict.fromkeys(G.neighbors_iter(v),1)
59
nextlevel.update(nbrs) # add neighbors of v
60
if (cutoff is not None and cutoff <= level): break
62
return seen # return all path lengths as dictionary
65
def all_pairs_shortest_path_length(G,cutoff=None):
66
""" Return dictionary of shortest path lengths between all nodes in G.
68
The dictionary only has keys for reachable node pairs.
70
>>> length=all_pairs_shortest_path_length(G)
71
>>> print length[1][4]
74
{0: 1, 1: 0, 2: 1, 3: 2, 4: 3}
77
cutoff is optional integer depth to stop the search - only
78
paths of length <= cutoff are returned.
83
paths[n]=single_source_shortest_path_length(G,n,cutoff=cutoff)
86
def shortest_path(G,source,target):
87
"""Return a list of nodes in G for a shortest path between source
90
There may be more than one shortest path. This returns only one.
93
return bidirectional_shortest_path(G,source,target)
96
def bidirectional_shortest_path(G,source,target):
98
Return list of nodes in a shortest path between source and target.
99
Return False if no path exists.
101
Also known as shortest_path.
104
# call helper to do the real work
105
results=_bidirectional_pred_succ(G,source,target)
107
return False # no path from source to target
110
# build path from pred+w+succ
124
def _bidirectional_pred_succ(G, source, target):
126
Bidirectional shortest path helper.
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.
132
# does BFS from both source and target and meets in the middle
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)
138
# handle either directed or undirected
140
Gpred=G.predecessors_iter
141
Gsucc=G.successors_iter
143
Gpred=G.neighbors_iter
144
Gsucc=G.neighbors_iter
146
# predecesssor and successors in search
150
# initialize fringes, start with forward
151
forward_fringe=[source]
152
reverse_fringe=[target]
154
while forward_fringe and reverse_fringe:
155
this_level=forward_fringe
160
forward_fringe.append(w)
162
if w in succ: return pred,succ,w # found path
163
this_level=reverse_fringe
169
reverse_fringe.append(w)
170
if w in pred: return pred,succ,w # found path
172
return False # no path found
175
def single_source_shortest_path(G,source,cutoff=None):
177
Return list of nodes in a shortest path between source
178
and all other nodes in G reachable from source.
180
There may be more than one shortest path between the
181
source and target nodes - this routine returns only one.
183
cutoff is optional integer depth to stop the search - only
184
paths of length <= cutoff are returned.
186
See also shortest_path and bidirectional_shortest_path.
188
level=0 # the current level
189
nextlevel={source:1} # list of nodes to check at next level
190
paths={source:[source]} # paths dictionary (paths to key from source)
197
for w in G.neighbors(v):
198
if not paths.has_key(w):
199
paths[w]=paths[v]+[w]
202
if (cutoff is not None and cutoff <= level): break
206
def all_pairs_shortest_path(G,cutoff=None):
207
""" Return dictionary of shortest paths between all nodes in G.
209
The dictionary only has keys for reachable node pairs.
211
cutoff is optional integer depth to stop the search - only
212
paths of length <= cutoff are returned.
214
See also floyd_warshall.
219
paths[n]=single_source_shortest_path(G,n,cutoff=cutoff)
223
def dijkstra_path(G,source,target):
225
Returns the shortest path from source to target in a weighted
226
graph G. Uses a bidirectional version of Dijkstra's algorithm.
228
Edge data must be numerical values for XGraph and XDiGraphs.
229
The weights are assigned to be 1 for Graphs and DiGraphs.
231
See also bidirectional_dijkstra for more information about the algorithm.
233
# (length,path)=bidirectional_dijkstra(G,source,target) # faster, needs test
235
(length,path)=single_source_dijkstra(G,source)
239
raise networkx.NetworkXError, \
240
"node %s not reachable from %s"%(source,target)
243
def dijkstra_path_length(G,source,target):
245
Returns the shortest path length from source to target in a weighted
246
graph G. Uses a bidirectional version of Dijkstra's algorithm.
248
Edge data must be numerical values for XGraph and XDiGraphs.
249
The weights are assigned to be 1 for Graphs and DiGraphs.
251
See also bidirectional_dijkstra for more information about the algorithm.
255
# (length,path)=bidirectional_dijkstra(G,source,target) # faster, needs test
257
(length,path)=single_source_dijkstra(G,source)
259
return length[target]
261
raise networkx.NetworkXError, \
262
"node %s not reachable from %s"%(source,target)
266
def bidirectional_dijkstra(G, source, target):
268
Dijkstra's algorithm for shortest paths using bidirectional search.
270
Returns a two-tuple (d,p) where d is the distance and p
271
is the path from the source to the target.
273
Distances are calculated as sums of weighted edges traversed.
275
Edges must hold numerical values for XGraph and XDiGraphs.
276
The weights are set to 1 for Graphs and DiGraphs.
278
In practice bidirectional Dijkstra is much more than twice as fast as
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.
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).
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
#Init: Forward Backward
298
dists = [{}, {}]# dictionary of final distances
299
paths = [{source:[source]}, {target:[target]}] # dictionary of paths
300
fringe = [[], []] #heap of (distance, node) tuples for extracting next node to expand
301
seen = [{source:0}, {target:0} ]#dictionary of distances to nodes seen
302
#initialize fringe heap
303
heapq.heappush(fringe[0], (0, source))
304
heapq.heappush(fringe[1], (0, target))
305
#neighs for extracting correct neighbor information
307
neighs = [G.successors_iter, G.predecessors_iter]
309
neighs = [G.neighbors_iter, G.neighbors_iter]
310
#variables to hold shortest discovered path
313
# if unweighted graph, set the weights to 1 on edges by
314
# introducing a get_edge method
315
if not hasattr(G,"get_edge"): G.get_edge=lambda x,y:1
317
while fringe[0] and fringe[1]:
319
# dir == 0 is forward direction and dir == 1 is back
321
# extract closest to expand
322
(dist, v )= heapq.heappop(fringe[dir])
324
# Shortest path to v has already been found
327
dists[dir][v] = dist #equal to seen[dir][v]
328
if v in dists[1-dir]:
329
# if we have scanned v in both directions we are done
330
# we have now discovered the shortest path
331
return (finaldist,finalpath)
332
for w in neighs[dir](v):
334
vwLength = dists[dir][v] + G.get_edge(v,w)
335
else: #back, must remember to change v,w->w,v
336
vwLength = dists[dir][v] + G.get_edge(w,v)
339
if vwLength < dists[dir][w]:
341
"Contradictory paths found: negative weights?"
342
elif w not in seen[dir] or vwLength < seen[dir][w]:
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
#see if this path is better than than the already
349
#discovered shortest path
350
totaldist = seen[0][w] + seen[1][w]
351
if finalpath == [] or finaldist > totaldist:
352
finaldist = totaldist
353
revpath = paths[1][w][:]
355
finalpath = paths[0][w] + revpath[1:]
359
#def dijkstra(G,source,target):
360
# return bidirectional_dijkstra(G,source,target)
363
def single_source_dijkstra_path(G,source):
365
Returns the shortest paths from source to all other reachable
366
nodes in a weighted graph G. Uses Dijkstra's algorithm.
368
Returns a dictionary of shortest path lengths keyed by source.
370
Edge data must be numerical values for XGraph and XDiGraphs.
371
The weights are assigned to be 1 for Graphs and DiGraphs.
373
See also single_source_dijkstra for more information about the algorithm.
376
(length,path)=single_source_dijkstra(G,source)
380
def single_source_dijkstra_path_length(G,source):
382
Returns the shortest path lengths from source to all other
383
reachable nodes in a weighted graph G. Uses Dijkstra's algorithm.
385
Returns a dictionary of shortest path lengths keyed by source.
387
Edge data must be numerical values for XGraph and XDiGraphs.
388
The weights are assigned to be 1 for Graphs and DiGraphs.
390
See also single_source_dijkstra for more information about the algorithm.
393
(length,path)=single_source_dijkstra(G,source)
397
def single_source_dijkstra(G,source,target=None):
399
Dijkstra's algorithm for shortest paths in a weighted graph G.
403
single_source_dijkstra_path() - shortest path list of nodes
405
single_source_dijkstra_path_length() - shortest path length
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.
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.
415
Optional target argument stops the search when target is found.
417
Based on the Python cookbook recipe (119466) at
418
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466
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).
424
See also 'bidirectional_dijkstra_path'
426
if source==target: return (0, [source])
427
dist = {} # dictionary of final distances
428
paths = {source:[source]} # dictionary of paths
430
fringe=[] # use heapq with (distance,label) tuples
431
heapq.heappush(fringe,(0,source))
433
(d,v)=heapq.heappop(fringe)
434
if v in dist: continue # already searched this node.
436
if v == target: break
437
for w in G.neighbors(v):
438
vw_dist = dist[v] + G.get_edge(v,w)
440
if vw_dist < dist[w]:
442
"Contradictory paths found: negative weights?"
443
elif w not in seen or vw_dist < seen[w]:
445
heapq.heappush(fringe,(vw_dist,w))
446
paths[w] = paths[v]+[w]
449
def dijkstra_predecessor_and_distance(G,source):
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.
457
This routine is intended for use with the betweenness centrality
458
algorithms in centrality.py.
462
dist = {} # dictionary of final distances
463
pred = {source:[]} # dictionary of predecessors
465
fringe=[] # use heapq with (distance,label) tuples
466
push(fringe,(0,source))
469
if v in dist: continue # already searched this node.
471
for w in G.neighbors(v):
472
vw_dist = dist[v] + G.get_edge(v,w)
474
if vw_dist < dist[w]:
476
"Contradictory paths found: negative weights?"
477
elif w not in seen or vw_dist < seen[w]:
479
push(fringe,(vw_dist,w))
481
elif vw_dist==seen[w]:
485
######################################################################
486
### Jeff A mods. Kept very local for now.
488
def floyd_warshall_array(graph):
490
The Floyd-Warshall algorithm for all pairs shortest paths.
492
Returns a tuple (distance,path) containing two arrays of shortest
493
distance and paths as a predecessor matrix.
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
503
This algorithm handles negative weights.
506
# A weight that's more than any path weight
508
for e in graph.edges():
509
HUGE_VAL += abs(graph.get_edge(e[0],e[1]))
521
dist[i][j] = 0 # arbitrary, just create slot
522
pred[i][j] = 0 # arbitrary, just create slot
526
elif graph.has_edge(i,j):
527
val = graph.get_edge(i,j)
528
dist_prev[i][j] = val
531
# no edge, distinct vertices
532
dist_prev[i][j] = HUGE_VAL
533
pred_prev[i][j] = -1 # None, but has to be numerically comparable
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]
541
pred[i][j] = pred_prev[k][j]
549
# The last time through the loop, we exchanged for nothing, so
550
# return the prev versions, since they're really the current
552
return dist_prev, pred_prev
553
######################################################################
555
def floyd_warshall(G,huge=1e30000):
557
The Floyd-Warshall algorithm for all pairs shortest paths.
559
Returns a tuple (distance,path) containing two dictionaries of shortest
560
distance and predecessor paths.
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.
566
For sparse graphs, see
568
all_pairs_shortest_path
569
all_pairs_shortest_path_length
571
which are based on Dijkstra's algorithm.
574
# dictionary-of-dictionaries representation for dist and pred
576
# initialize path distance dictionary to be the adjacency matrix
577
# but with sentinal value "huge" where there is no edge
578
# also set the distance to self to 0 (zero diagonal)
580
# initialize predecessor dictionary
586
dist[u][v]=G.get_edge(u,v)
591
dist[u][u]=0 # set 0 distance to self
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]
602
def predecessor(G,source,target=None,cutoff=None,return_seen=None):
603
""" Returns dictionary of predecessors for the path from source to all
606
Optional target returns only predecessors between source and target.
607
Cutoff is a limit on the number of hops traversed.
609
Example for the path graph 0-1-2-3
615
{0: [], 1: [0], 2: [1], 3: [2]}
618
level=0 # the current level
619
nextlevel=[source] # list of nodes to check at next level
620
seen={source:level} # level (number of hops) when seen in BFS
621
pred={source:[]} # predecessor dictionary
627
for w in G.neighbors(v):
628
if (not seen.has_key(w)):
632
elif (seen[w]==level):# add v to predecessor list if it
633
pred[w].append(v) # is at the correct level
634
if (cutoff and cutoff <= level):
637
if target is not None:
639
if not pred.has_key(target): return ([],-1) # No predecessor
640
return (pred[target],seen[target])
642
if not pred.has_key(target): return [] # No predecessor
653
suite = doctest.DocFileSuite('tests/shortest_path.txt',package='networkx')
657
if __name__ == "__main__":
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]
664
# directory of networkx package (relative to this)
665
nxbase=sys.path[0]+os.sep+os.pardir
666
sys.path.insert(0,nxbase) # prepend to search path
667
unittest.TextTestRunner().run(_test_suite())
added
removed
networkx/path.py
