120 lines
4.3 KiB
Python
120 lines
4.3 KiB
Python
# Dijkstra's algorithm for shortest paths
|
|
# David Eppstein, UC Irvine, 4 April 2002
|
|
|
|
# http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117228
|
|
from utils.priodict import priorityDictionary
|
|
|
|
def Dijkstra(G,start,end=None):
|
|
"""
|
|
Find shortest paths from the start vertex to all vertices nearer than or equal to the end.
|
|
|
|
The input graph G is assumed to have the following representation:
|
|
A vertex can be any object that can be used as an index into a dictionary.
|
|
G is a dictionary, indexed by vertices. For any vertex v, G[v] is itself a dictionary,
|
|
indexed by the neighbors of v. For any edge v->w, G[v][w] is the length of the edge.
|
|
This is related to the representation in <http://www.python.org/doc/essays/graphs.html>
|
|
where Guido van Rossum suggests representing graphs as dictionaries mapping vertices
|
|
to lists of outgoing edges, however dictionaries of edges have many advantages over lists:
|
|
they can store extra information (here, the lengths), they support fast existence tests,
|
|
and they allow easy modification of the graph structure by edge insertion and removal.
|
|
Such modifications are not needed here but are important in many other graph algorithms.
|
|
Since dictionaries obey iterator protocol, a graph represented as described here could
|
|
be handed without modification to an algorithm expecting Guido's graph representation.
|
|
|
|
Of course, G and G[v] need not be actual Python dict objects, they can be any other
|
|
type of object that obeys dict protocol, for instance one could use a wrapper in which vertices
|
|
are URLs of web pages and a call to G[v] loads the web page and finds its outgoing links.
|
|
|
|
The output is a pair (D,P) where D[v] is the distance from start to v and P[v] is the
|
|
predecessor of v along the shortest path from s to v.
|
|
|
|
Dijkstra's algorithm is only guaranteed to work correctly when all edge lengths are positive.
|
|
This code does not verify this property for all edges (only the edges examined until the end
|
|
vertex is reached), but will correctly compute shortest paths even for some graphs with negative
|
|
edges, and will raise an exception if it discovers that a negative edge has caused it to make a mistake.
|
|
"""
|
|
|
|
D = {} # dictionary of final distances
|
|
P = {} # dictionary of predecessors
|
|
Q = priorityDictionary() # estimated distances of non-final vertices
|
|
Q[start] = 0
|
|
|
|
for v in Q:
|
|
|
|
D[v] = Q[v]
|
|
if v == end: break
|
|
|
|
for w in G[v]:
|
|
vwLength = D[v] + G[v][w]
|
|
if w in D:
|
|
if vwLength < D[w]:
|
|
raise ValueError("Dijkstra: found better path to already-final vertex")
|
|
elif w not in Q or vwLength < Q[w]:
|
|
Q[w] = vwLength
|
|
P[w] = v
|
|
|
|
return (D,P)
|
|
|
|
def shortestPath(G,start,end):
|
|
"""
|
|
Find a single shortest path from the given start vertex to the given end vertex.
|
|
The input has the same conventions as Dijkstra().
|
|
The output is a list of the vertices in order along the shortest path.
|
|
"""
|
|
|
|
D,P = Dijkstra(G,start,end)
|
|
|
|
Path = []
|
|
while 1:
|
|
Path.append(end)
|
|
if end == start: break
|
|
end = P[end]
|
|
Path.reverse()
|
|
return Path
|
|
|
|
class Graph:
|
|
def __init__(self):
|
|
self.graph = {}
|
|
|
|
def add_vertex(self, vertex):
|
|
self.graph[vertex] = {}
|
|
|
|
def del_vertex(self, vertex):
|
|
del self.graph[vertex]
|
|
|
|
def is_vertex(self, vertex):
|
|
if vertex in self.graph:
|
|
return True
|
|
else:
|
|
return False
|
|
|
|
def add_edge(self, vertex_start, vertex_end, weight, data):
|
|
self.graph[vertex_start][vertex_end] = weight
|
|
|
|
def del_edge(self, vertex_start, vertex_end):
|
|
del self.graph[vertex_start][vertex_end]
|
|
|
|
def is_edge(self, vertex_start, vertex_end):
|
|
if vertex_start in self.graph and vertex_end in self.graph[vertex_start]:
|
|
return True
|
|
else:
|
|
return False
|
|
|
|
def get_graph(self):
|
|
return self.graph
|
|
|
|
def __getitem__(self, key):
|
|
return self.graph.get(key, {})
|
|
|
|
def __len__(self):
|
|
return len(self.graph)
|
|
|
|
# example, CLR p.528
|
|
# G = {'s': {'u':10, 'x':5},
|
|
# 'u': {'v':1, 'x':2},
|
|
# 'v': {'y':4},
|
|
# 'x':{'u':3,'v':9,'y':2},
|
|
# 'y':{'s':7,'v':6}}
|
|
#
|
|
# print Dijkstra(G,'s')
|
|
# print shortestPath(G,'s','v')
|