Dijkstra’s Algorithm
January 4, 2011
We follow the implementation given in Section 24.3 of the third edition, published in 2009, of Introduction to Algorithms by Thomas Cormen, Charles Leiserson, Ronald Rivest and Clifford Stein. (hereafter referred to as CLRS). In it, vertices are given a number of attributes; we begin with a simple vertex class to collect them all in one spot:
class Vertex(object):
def __init__(self, adj={}, dist=float("inf"), name=None, pred=None):
self.adj = adj
self.dist = dist
self.name = name
self.pred = pred
return
def __cmp__(self, other):
return cmp(self.dist, other.dist)
def __repr__(self):
return self.name
A vertex has a distance parameter, a name, and a predecessor. In CLRS, vertices also have an adjacency list and edge weights are recorded in an external structure. We instead opt to have each vertex’s adj attribute be a Python dictionary, where each key is an adjacent vertex and each value is the weight of the edge between them. We also give vertices a __cmp__ method to compare vertices by distance and a __repr__ method is included to give human readable print out.
The implementation of Dijkstra’s Algorithm in CLRS requires a min-priority queue; interestingly, this queue determines the speed of the algorithm as a whole, because we need to constantly retrieve the vertex of minimum distance and update the key of a node in the queue whenever a vertex’s distance estimate changes. While CLRS recommends a Fibonacci heap, we’ll use pairing-heaps which we studied in a previous exercise. Pairing heaps have most of the efficiency of Fibonacci heaps, while being easier to implement.
We’ll represent a digraph with a Python dictionary of string –> vertex pairs. First off, we have two procedures to build our digraph D out of edges:
def add_edge(D, u, v, weight):
if u not in D:
D[u] = Vertex(name=u, adj={})
if v not in D:
D[v] = Vertex(name=v, adj={})
D[u].adj[v] = weight
return
def add_edges(D, edges):
for edge in edges:
add_edge(D, *edge)
return
When adding an edge, we first ensure both vertices are in the graph. Then the head vertex’s adjacency list is updated with tail vertex and the weight of the edge between them. The add_edges procedure is included for convenience’s sake, so we don’t have to build the digraph one edge at a time.
Next, our two helper functions: init_single_source and relax. The first readies the digraph for work on the single source shortest path problem, while the latter updates each vertex when a shorter path is found to it:
def init_single_source(D, s):
for v in D:
D[v].dist = float("inf")
D[v].pred = None
D[s].dist = 0
return
def relax(D, u, v):
d = D[u].dist + D[u].adj[v]
if D[v].dist > d:
D[v].dist = d
D[v].pred = u
return
The main procedure is dijkstra. First, we add each vertex (D.values() is a list of all the vertices in D) to the priority queue. Next we iteratively step through all the vertices of the digraph (indexed by distance from the source), relaxing each outward edge. We also clean up the queue with merge_pairs so that the queue is again ordered by distance after relaxing edges.
def dijkstra(D, s):
init_single_source(D, s)
Q = make_heap()
for v in D.values():
Q = insert(v, Q)
while Q:
u, Q = find_min(Q), delete_min(Q)
for v in u.adj:
relax(D, u.name, v)
Q = merge_pairs(Q)
return
Finally, we build the shortest path by traversing backwards through the predecessor subtree created by the algorithm. We record the path with a list, appending on the right, and then reverse the list to get the path in order:
def find_shortest_path(D, s, f):
dijkstra(D, s)
path, v = [f], D[f].pred
while v is not None:
path.append(v)
v = D[v].pred
path.reverse()
return path
Testing on the digraph given in our picture:
if __name__ == "__main__":
D = {}
add_edges(D, [('a', 'c', 2), ('a', 'd', 6),
('b', 'a', 3), ('b', 'd', 8),
('c', 'd', 7), ('c', 'e', 5),
('d', 'e', 10)])
print find_shortest_path(D, 'a', 'e')
# Output: ['a', 'c', 'e']
The code including the priority-queue is available on http://codepad.org/lRUh1tq8.
Programming Praxis 
[…] today’s Programming Praxis, our task is to implement Dijkstra’s shortest path algorithm. Let’s […]
My Haskell solution (see http://bonsaicode.wordpress.com/2011/01/04/programming-praxis-dijkstra%E2%80%99s-algorithm/ for a version with comments):
import Data.List import qualified Data.List.Key as K import Data.Map ((!), fromList, fromListWith, adjust, keys, Map) buildGraph :: Ord a => [(a, a, Float)] -> Map a [(a, Float)] buildGraph g = fromListWith (++) $ g >>= \(a,b,d) -> [(a,[(b,d)]), (b,[(a,d)])] dijkstra :: Ord a => a -> Map a [(a, Float)] -> Map a (Float, Maybe a) dijkstra source graph = f (fromList [(v, (if v == source then 0 else 1/0, Nothing)) | v <- keys graph]) (keys graph) where f ds [] = ds f ds q = f (foldr relax ds $ graph ! m) (delete m q) where m = K.minimum (fst . (ds !)) q relax (e,d) = adjust (min (fst (ds ! m) + d, Just m)) e shortestPath :: Ord a => a -> a -> Map a [(a, Float)] -> [a] shortestPath from to graph = reverse $ f to where f x = x : maybe [] f (snd $ dijkstra from graph ! x) main :: IO () main = do let g = buildGraph [('a','c',2), ('a','d',6), ('b','a',3), ('b','d',8), ('c','d',7), ('c','e',5), ('d','e',10)] print $ shortestPath 'a' 'e' g == "ace"[…] Programming Praxis: Dijkstra’s Algorithm […]
My commented version: http://www.gleocadie.net/?p=641&lang=en
def dijkstra2(g, sn, en, sz): g.setdefault(sn, []) nexts = g[sn] if sn == en: return ([en], sz) elif sn in memo and memo[sn] != None: # memoization return memo[sn] elif not nexts or sn in memo: # is a cycle? return ([], -1) else: def update_path(e, l): return ([e] + l[0], l[1]) def f(r): return r[1] != -1 memo[sn] = None m = filter(lambda x: f(update_path(sn, dijkstra2(g, x[0], en, sz + x[1]))), nexts) try: res = min(m, key=lambda x: x[1]) memo[sn] = res return res except Exception: # empty list passed to min return ([], -1)My try in Rexx
/* Daten von: http://de.wikipedia.org/wiki/Dijkstra-Algorithmus */ MAX = 99999 orte = 'F MA W S KS KA E N A M' strecken = 'F-MA-85 F-W-217 F-KS-173 MA-KA-80 W-E-186 W-N-103', 'S-N-183 KA-A-250 N-M-167 KS-M-502 A-M-84' /* Die Entfernungen (d.) und Vorgänger (p.) werden */ /* durch den ort indiziert, z.B. d.MA oder p.M */ d. = '' p. = '' q = orte start = 'F' ziel = 'M' wi = 0 do while wi < words(orte) wi = wi + 1 w = word(orte, wi) if w == start then d.w = 0 else d.w = MAX p.w = '' end do while words(q) > 0 q = sort(q) u = word(q, 1) q = delword(q, 1, 1) call relax u,strecken end say translate(strip(ausgabe(ziel, '')),'>',' ') '=' d.ziel 'KM' exit sort: procedure expose d. parse arg q sq. = '' si = 0 do words(q) si = si + 1 w = word(q, si) sq.si = right(d.w, 5, '0')||w end sq.0 = si chg = 1 do while chg = 1 chg = 0 do i = 1 to (sq.0 - 1) do j = (i + 1) to sq.0 if sq.i > sq.j then do tmp = sq.i sq.i = sq.j sq.j = tmp chg = 1 end end end end q = '' do i = 1 to sq.0 q = q substr(sq.i, 6) end return strip(q) relax: procedure expose d. p. parse arg akt,kanten do while length(kanten) > 0 parse value kanten with kante kanten parse value kante with von'-'nach'-'entf select when akt == von then nb = nach when akt == nach then nb = von otherwise iterate end neu = d.akt + entf if d.nb > neu then do d.nb = neu p.nb = akt end end return ausgabe: parse arg vorg, route if p.vorg == '' then return strip(reverse(route vorg)) return ausgabe(p.vorg,route vorg)slightly optimized REXX (no double init, no sort but select for next neighbour)
MAX = 99999 orte = 'F MA W S KS KA E N A M' strecken = 'F-MA-85 F-W-217 F-KS-173 MA-KA-80 W-E-186 W-N-103', 'S-N-183 KA-A-250 N-M-167 KS-M-502 A-M-84' start = 'F' ziel = 'M' d. = MAX /* je Ort: Entfernung von start */ d.start = 0 p. = '' /* je Ort: Vorgänger auf kürzestem Weg */ q = orte do while words(q) > 0 u = n_nb(q) q = delword(q, wordpos(u,q), 1) call relax u,strecken end say translate(strip(ausgabe(ziel, '')),'>',' ') '=' d.ziel 'KM' exit n_nb: procedure expose d. MAX parse arg q min = MAX rw = '' do i = 1 to words(q) w = word(q, i) if d.w < min then do min = d.w rw = w end end return rw relax: procedure expose d. p. parse arg akt,kanten do while length(kanten) > 0 parse value kanten with kante kanten parse value kante with von'-'nach'-'entf select when akt == von then nb = nach when akt == nach then nb = von otherwise iterate end neu = d.akt + entf if d.nb > neu then do d.nb = neu p.nb = akt end end return ausgabe: parse arg vorg, route if p.vorg == '' then return strip(reverse(route vorg)) return ausgabe(p.vorg,route vorg)infinity = float('inf') def graph_from_edges(elist, directed=True): '''turns list of edges [(fm, to, weight), ...] into a graph in the form of nested dictionaries as used by dijkstra() below. ''' graph = {} for fm, to, wt in elist: if fm not in graph: graph[fm] = {} graph[fm][to] = wt if to not in graph: graph[to] = {} if not directed: graph[to][fm] = wt return graph def dijkstra(graph, source, destination=None): '''Calculate minimum path from source to destination, (defaults to all reachable nodes. Returns a dict of node:(cost,prev) items. Almost verbtim from pseudocode in Wikipedia article: http://en.wikipedia.org/wiki/Dijkstra's_algorithm. ''' dist = {v:infinity for v in graph.keys()} prev = {v:None for v in graph.keys()} dist[source] = 0 Q = set(graph.keys()) while Q: u = min(Q, key=dist.get) if dist[u] == infinity: print "disconnected graph" break if u == destination: break Q.remove(u) for v,w in graph[u].items(): alt = dist[u] + w if alt < dist[v]: dist[v] = alt prev[v] = u return {k:(dist[k], prev[k]) for k in graph.keys()}