1
# -*- coding: utf-8 -*-
3
Shortest path algorithms for weighed graphs.
5
__author__ = """\n""".join(['Aric Hagberg <hagberg@lanl.gov>',
6
'Loïc Séguin-C. <loicseguin@gmail.com>'])
7
# Copyright (C) 2004-2010 by
8
# Aric Hagberg <hagberg@lanl.gov>
9
# Dan Schult <dschult@colgate.edu>
10
# Pieter Swart <swart@lanl.gov>
11
# All rights reserved.
14
__all__ = ['dijkstra_path',
15
'dijkstra_path_length',
16
'bidirectional_dijkstra',
17
'single_source_dijkstra_path',
18
'single_source_dijkstra_path_length',
19
'all_pairs_dijkstra_path',
20
'all_pairs_dijkstra_path_length',
21
'single_source_dijkstra',
22
'dijkstra_predecessor_and_distance',
29
def dijkstra_path(G,source,target, weight = 'weight'):
30
"""Returns the shortest path from source to target in a weighted graph G.
42
weight: string, optional
43
Edge data key corresponding to the edge weight
48
List of nodes in a shortest path.
52
>>> G=nx.path_graph(5)
53
>>> print(nx.dijkstra_path(G,0,4))
58
Uses a bidirectional version of Dijkstra's algorithm.
59
Edge weight attributes must be numerical.
63
bidirectional_dijkstra()
65
# (length,path)=bidirectional_dijkstra(G,source,target) # faster, needs test
67
(length,path)=single_source_dijkstra(G,source, weight = weight)
71
raise nx.NetworkXError("node %s not reachable from %s"%(source,target))
74
def dijkstra_path_length(G,source,target, weight = 'weight'):
75
"""Returns the shortest path length from source to target in a weighted graph G.
80
G : NetworkX graph, weighted
83
starting node for path
88
weight: string, optional
89
Edge data key corresponding to the edge weight
99
If no path exists between source and target.
103
>>> G=nx.path_graph(5) # a weighted graph by default
104
>>> print(nx.dijkstra_path_length(G,0,4))
109
Edge weight attributes must be numerical.
113
bidirectional_dijkstra()
117
# (length,path)=bidirectional_dijkstra(G,source,target) # faster, needs test
119
(length,path)=single_source_dijkstra(G,source, weight = weight)
121
return length[target]
123
raise nx.NetworkXError("node %s not reachable from %s"%(source,target))
127
def bidirectional_dijkstra(G, source, target, weight = 'weight'):
128
"""Dijkstra's algorithm for shortest paths using bidirectional search.
140
weight: string, optional
141
Edge data key corresponding to the edge weight
146
Shortest path length.
148
Returns a tuple of two dictionaries keyed by node.
149
The first dicdtionary stores distance from the source.
150
The second stores the path from the source to that node.
152
Raise an exception if no path exists.
158
If no path exists between source and target.
162
>>> G=nx.path_graph(5)
163
>>> length,path=nx.bidirectional_dijkstra(G,0,4)
171
Edge weight attributes must be numerical.
172
Distances are calculated as sums of weighted edges traversed.
174
In practice bidirectional Dijkstra is much more than twice as fast as
177
Ordinary Dijkstra expands nodes in a sphere-like manner from the
178
source. The radius of this sphere will eventually be the length
179
of the shortest path. Bidirectional Dijkstra will expand nodes
180
from both the source and the target, making two spheres of half
181
this radius. Volume of the first sphere is pi*r*r while the
182
others are 2*pi*r/2*r/2, making up half the volume.
184
This algorithm is not guaranteed to work if edge weights
185
are negative or are floating point numbers
186
(overflows and roundoff errors can cause problems).
193
if source is None or target is None:
194
raise NetworkXException(
195
"Bidirectional Dijkstra called with no source or target")
196
if source == target: return (0, [source])
197
#Init: Forward Backward
198
dists = [{}, {}]# dictionary of final distances
199
paths = [{source:[source]}, {target:[target]}] # dictionary of paths
200
fringe = [[], []] #heap of (distance, node) tuples for extracting next node to expand
201
seen = [{source:0}, {target:0} ]#dictionary of distances to nodes seen
202
#initialize fringe heap
203
heapq.heappush(fringe[0], (0, source))
204
heapq.heappush(fringe[1], (0, target))
205
#neighs for extracting correct neighbor information
207
neighs = [G.successors_iter, G.predecessors_iter]
209
neighs = [G.neighbors_iter, G.neighbors_iter]
210
#variables to hold shortest discovered path
214
while fringe[0] and fringe[1]:
216
# dir == 0 is forward direction and dir == 1 is back
218
# extract closest to expand
219
(dist, v )= heapq.heappop(fringe[dir])
221
# Shortest path to v has already been found
224
dists[dir][v] = dist #equal to seen[dir][v]
225
if v in dists[1-dir]:
226
# if we have scanned v in both directions we are done
227
# we have now discovered the shortest path
228
return (finaldist,finalpath)
230
for w in neighs[dir](v):
232
if G.is_multigraph():
233
minweight=min((dd.get(weight,1)
234
for k,dd in G[v][w].items()))
236
minweight=G[v][w].get(weight,1)
237
vwLength = dists[dir][v] + minweight #G[v][w].get(weight,1)
238
else: #back, must remember to change v,w->w,v
239
if G.is_multigraph():
240
minweight=min((dd.get(weight,1)
241
for k,dd in G[w][v].items()))
243
minweight=G[w][v].get(weight,1)
244
vwLength = dists[dir][v] + minweight #G[w][v].get(weight,1)
247
if vwLength < dists[dir][w]:
248
raise ValueError("Contradictory paths found: negative weights?")
249
elif w not in seen[dir] or vwLength < seen[dir][w]:
251
seen[dir][w] = vwLength
252
heapq.heappush(fringe[dir], (vwLength,w))
253
paths[dir][w] = paths[dir][v]+[w]
254
if w in seen[0] and w in seen[1]:
255
#see if this path is better than than the already
256
#discovered shortest path
257
totaldist = seen[0][w] + seen[1][w]
258
if finalpath == [] or finaldist > totaldist:
259
finaldist = totaldist
260
revpath = paths[1][w][:]
262
finalpath = paths[0][w] + revpath[1:]
266
#def dijkstra(G,source,target):
267
# return bidirectional_dijkstra(G,source,target)
270
def single_source_dijkstra_path(G,source, weight = 'weight'):
271
"""Compute shortest path between source and all other reachable nodes for a weighted graph.
278
Starting node for path.
280
weight: string, optional
281
Edge data key corresponding to the edge weight
286
Dictionary of shortest path lengths keyed by target.
290
>>> G=nx.path_graph(5)
291
>>> path=nx.single_source_dijkstra_path(G,0)
297
Edge weight attributes must be numerical.
301
single_source_dijkstra()
304
(length,path)=single_source_dijkstra(G,source, weight = weight)
308
def single_source_dijkstra_path_length(G,source, weight = 'weight'):
309
"""Compute shortest path length between source and all other reachable nodes for a weighted graph.
316
Starting node for path
318
weight: string, optional
319
Edge data key corresponding to the edge weight
324
Dictionary of shortest paths keyed by target.
328
>>> G=nx.path_graph(5)
329
>>> length=nx.single_source_dijkstra_path_length(G,0)
333
{0: 0, 1: 1, 2: 2, 3: 3, 4: 4}
337
Edge data must be numerical values for XGraph and XDiGraphs.
342
single_source_dijkstra()
345
(length,path)=single_source_dijkstra(G,source, weight = weight)
349
def single_source_dijkstra(G,source,target=None,cutoff=None,weight='weight'):
350
"""Compute shortest paths and lengths in a weighted graph G.
352
Uses Dijkstra's algorithm for shortest paths.
359
Starting node for path
361
target : node label, optional
364
cutoff : integer or float, optional
365
Depth to stop the search. Only paths of length <= cutoff are returned.
369
distance,path : dictionaries
370
Returns a tuple of two dictionaries keyed by node.
371
The first dictionary stores distance from the source.
372
The second stores the path from the source to that node.
377
>>> G=nx.path_graph(5)
378
>>> length,path=nx.single_source_dijkstra(G,0)
382
{0: 0, 1: 1, 2: 2, 3: 3, 4: 4}
388
Distances are calculated as sums of weighted edges traversed.
389
Edges must hold numerical values for Graph and DiGraphs.
391
Based on the Python cookbook recipe (119466) at
392
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466
394
This algorithm is not guaranteed to work if edge weights
395
are negative or are floating point numbers
396
(overflows and roundoff errors can cause problems).
400
single_source_dijkstra_path()
401
single_source_dijkstra_path_length()
404
if source==target: return (0, [source])
405
dist = {} # dictionary of final distances
406
paths = {source:[source]} # dictionary of paths
408
fringe=[] # use heapq with (distance,label) tuples
409
heapq.heappush(fringe,(0,source))
411
(d,v)=heapq.heappop(fringe)
412
if v in dist: continue # already searched this node.
414
if v == target: break
415
#for ignore,w,edgedata in G.edges_iter(v,data=True):
416
#is about 30% slower than the following
417
if G.is_multigraph():
419
for w,keydata in list(G[v].items()):
420
minweight=min((dd.get(weight,1)
421
for k,dd in keydata.items()))
422
edata.append((w,{weight:minweight}))
424
edata=iter(G[v].items())
427
for w,edgedata in edata:
428
vw_dist = dist[v] + edgedata.get(weight,1)
429
if cutoff is not None:
433
if vw_dist < dist[w]:
434
raise ValueError("Contradictory paths found: negative weights?")
435
elif w not in seen or vw_dist < seen[w]:
437
heapq.heappush(fringe,(vw_dist,w))
438
paths[w] = paths[v]+[w]
441
def dijkstra_predecessor_and_distance(G,source, weight = 'weight'):
442
"""Compute shorest path length and predecessors on shortest paths in weighted graphs.
449
Starting node for path
451
weight: string, optional
452
Edge data key corresponding to the edge weight
456
pred,distance : dictionaries
457
Returns two dictionaries representing a list of predecessors
458
of a node and the distance to each node.
462
The list of predecessors contains more than one element only when
463
there are more than one shortest paths to the key node.
467
dist = {} # dictionary of final distances
468
pred = {source:[]} # dictionary of predecessors
470
fringe=[] # use heapq with (distance,label) tuples
471
push(fringe,(0,source))
474
if v in dist: continue # already searched this node.
476
if G.is_multigraph():
478
for w,keydata in G[v].items():
479
minweight=min((dd.get(weight,1)
480
for k,dd in keydata.items()))
481
edata.append((w,{weight:minweight}))
483
edata=iter(G[v].items())
484
for w,edgedata in edata:
485
vw_dist = dist[v] + edgedata.get(weight,1)
487
if vw_dist < dist[w]:
488
raise ValueError("Contradictory paths found: negative weights?")
489
elif w not in seen or vw_dist < seen[w]:
491
push(fringe,(vw_dist,w))
493
elif vw_dist==seen[w]:
497
def all_pairs_dijkstra_path_length(G, weight = 'weight'):
498
""" Compute shortest path lengths between all nodes in a weighted graph.
504
weight: string, optional
505
Edge data key corresponding to the edge weight
509
distance : dictionary
510
Dictionary, keyed by source and target, of shortest path lengths.
514
>>> G=nx.path_graph(5)
515
>>> length=nx.all_pairs_dijkstra_path_length(G)
516
>>> print(length[1][4])
519
{0: 1, 1: 0, 2: 1, 3: 2, 4: 3}
523
The dictionary returned only has keys for reachable node pairs.
527
paths[n]=single_source_dijkstra_path_length(G,n, weight = weight)
530
def all_pairs_dijkstra_path(G, weight = 'weight'):
531
""" Compute shortest paths between all nodes in a weighted graph.
537
weight: string, optional
538
Edge data key corresponding to the edge weight
542
distance : dictionary
543
Dictionary, keyed by source and target, of shortest paths.
547
>>> G=nx.path_graph(5)
548
>>> path=nx.all_pairs_dijkstra_path(G)
549
>>> print(path[0][4])
559
paths[n]=single_source_dijkstra_path(G,n, weight = weight)
562
def bellman_ford(G, source, weight = 'weight'):
563
"""Compute shortest path lengths and predecessors on shortest paths
566
The algorithm has a running time of O(mn) where n is the number of nodes
567
and n is the number of edges.
572
The algorithm works for all types of graphs, including directed
573
graphs and multigraphs.
576
Starting node for path
578
weight: string, optional
579
Edge data key corresponding to the edge weight
583
pred,dist : dictionaries
584
Returns two dictionaries representing a list of predecessors
585
of a node and the distance from the source to each node. The
586
dictionaries are keyed by target node label.
591
If the (di)graph contains a negative cost (di)cycle, the
592
algorithm raises an exception to indicate the presence of the
593
negative cost (di)cycle.
597
>>> import networkx as nx
598
>>> G = nx.path_graph(5, create_using = nx.DiGraph())
599
>>> pred, dist = nx.bellman_ford(G, 0)
601
{0: None, 1: 0, 2: 1, 3: 2, 4: 3}
603
{0: 0, 1: 1, 2: 2, 3: 3, 4: 4}
605
>>> from nose.tools import assert_raises
606
>>> G = nx.cycle_graph(5)
607
>>> G[1][2]['weight'] = -7
608
>>> assert_raises(nx.NetworkXError, nx.bellman_ford, G, 0)
612
The dictionaries returned only have keys for nodes reachable from
615
In the case where the (di)graph is not connected, if a component
616
not containing the source contains a negative cost (di)cycle, it
617
will not be detected.
621
if not G.is_directed():
627
pred = {source: None}
629
if G.number_of_nodes() == 1:
632
def process_edge(u, v, weight):
633
# Just a helper function for the main algorithm below.
634
if dist.get(u) is not None:
635
if dist.get(v) is None or dist[v] > dist[u] + weight:
636
dist[v] = dist[u] + weight
641
for i in range(G.number_of_nodes()):
643
for u, v in G.edges():
644
if G.is_multigraph():
645
edata = min([eattr.get(weight, 1)
646
for eattr in G[u][v].values()])
648
edata = G[u][v].get(weight, 1)
649
if not process_edge(u, v, edata):
652
if not (v, u) in G.edges():
653
if not process_edge(v, u, edata):
658
if i + 1 == G.number_of_nodes():
659
raise nx.NetworkXError("Negative cost cycle detected.")
added
removed
networkx/algorithms/shortest_paths/weighted.py
