## 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.

Pages: 1 2

### 7 Responses to “Dijkstra’s Algorithm”

1. […] today’s Programming Praxis, our task is to implement Dijkstra’s shortest path algorithm. Let’s […]

```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"
```
3. […] Programming Praxis: Dijkstra’s Algorithm […]

```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, l)
def f(r): return r != -1

memo[sn] = None
m = filter(lambda x:
f(update_path(sn, dijkstra2(g, x, en, sz + x))),
nexts)
try:
res = min(m, key=lambda x: x)
memo[sn] = res
return res
except Exception: # empty list passed to min
return ([], -1)
```
5. Rainer said

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)

```
6. Rainer said

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)

```
7. Mike said
```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()}
```