dijkstra.py
Go to the documentation of this file.
00001 ## {{{ http://code.activestate.com/recipes/119466/ (r1)
00002 # Dijkstra's algorithm for shortest paths
00003 # David Eppstein, UC Irvine, 4 April 2002
00004 
00005 # http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117228
00006 from priodict import priorityDictionary
00007 
00008 def Dijkstra(G,start,end=None):
00009         """
00010         Find shortest paths from the start vertex to all
00011         vertices nearer than or equal to the end.
00012 
00013         The input graph G is assumed to have the following
00014         representation: A vertex can be any object that can
00015         be used as an index into a dictionary.  G is a
00016         dictionary, indexed by vertices.  For any vertex v,
00017         G[v] is itself a dictionary, indexed by the neighbors
00018         of v.  For any edge v->w, G[v][w] is the length of
00019         the edge.  This is related to the representation in
00020         <http://www.python.org/doc/essays/graphs.html>
00021         where Guido van Rossum suggests representing graphs
00022         as dictionaries mapping vertices to lists of neighbors,
00023         however dictionaries of edges have many advantages
00024         over lists: they can store extra information (here,
00025         the lengths), they support fast existence tests,
00026         and they allow easy modification of the graph by edge
00027         insertion and removal.  Such modifications are not
00028         needed here but are important in other graph algorithms.
00029         Since dictionaries obey iterator protocol, a graph
00030         represented as described here could be handed without
00031         modification to an algorithm using Guido's representation.
00032 
00033         Of course, G and G[v] need not be Python dict objects;
00034         they can be any other object that obeys dict protocol,
00035         for instance a wrapper in which vertices are URLs
00036         and a call to G[v] loads the web page and finds its links.
00037         
00038         The output is a pair (D,P) where D[v] is the distance
00039         from start to v and P[v] is the predecessor of v along
00040         the shortest path from s to v.
00041         
00042         Dijkstra's algorithm is only guaranteed to work correctly
00043         when all edge lengths are positive. This code does not
00044         verify this property for all edges (only the edges seen
00045         before the end vertex is reached), but will correctly
00046         compute shortest paths even for some graphs with negative
00047         edges, and will raise an exception if it discovers that
00048         a negative edge has caused it to make a mistake.
00049         """
00050 
00051         D = {}  # dictionary of final distances
00052         P = {}  # dictionary of predecessors
00053         Q = priorityDictionary()   # est.dist. of non-final vert.
00054         Q[start] = 0
00055         
00056         for v in Q:
00057                 D[v] = Q[v]
00058                 if v == end: break
00059                 
00060                 for w in G[v]:
00061                         vwLength = D[v] + G[v][w]
00062                         if w in D:
00063                                 if vwLength < D[w]:
00064                                         raise ValueError, \
00065   "Dijkstra: found better path to already-final vertex"
00066                         elif w not in Q or vwLength < Q[w]:
00067                                 Q[w] = vwLength
00068                                 P[w] = v
00069         
00070         return (D,P)
00071                         
00072 def shortestPath(G,start,end):
00073         """
00074         Find a single shortest path from the given start vertex
00075         to the given end vertex.
00076         The input has the same conventions as Dijkstra().
00077         The output is a list of the vertices in order along
00078         the shortest path.
00079         """
00080 
00081         D,P = Dijkstra(G,start,end)
00082         Path = []
00083         while 1:
00084                 Path.append(end)
00085                 if end == start: break
00086                 end = P[end]
00087         Path.reverse()
00088         return Path
00089 ## end of http://code.activestate.com/recipes/119466/ }}}
00090 


k-sap_pkg
Author(s): Joao Manuel Leitao Quintas
autogenerated on Mon Jan 6 2014 11:25:40