## Dijkstra’s Algorithm

### January 4, 2011 [ Today’s exercise was written by guest author Graham Enos, a PhD student in the Applied Mathematics program at UNC Charlotte, with solution in Python rather than Scheme. Suggestions for exercises are always welcome, or you may wish to contribute your own exercise; feel free to contact me if you are interested. ]

We’ve worked with directed graphs (“digraphs”) in a recent exercise. Today’s exercise is another graph theoretical procedure with many applications: Dijkstra’s Algorithm.

Published by Edgar Dijkstra in 1959, this algorithm searches a digraph for the shortest paths beginning at a specified vertex; to quote the Wikipedia article,

For example, if the vertices of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra’s algorithm can be used to find the shortest route between one city and all other cities. As a result, the shortest path first is widely used in network routing protocols, most notably IS-IS and OSPF (Open Shortest Path First).

For instance, in the digraph pictured at right, the shortest path from vertex a to e is [a, c, e]. This path has a length of 7, which is shorter than the path [a, d, e] (which has a length of 16).

The algorithm works its way through the vertices, indexed by their estimated distance from the starting point. At each vertex, the procedure “relaxes” all its outward edges, updating distance and predecessor estimates accordingly. Once complete, the algorithm has in effect constructed a subtree of the graph that gives all the shortest distance paths from the starting vertex to any other vertex in the graph via the predecessor attribute. The shortest path to the desired finishing vertex can then be reconstructed by traversing the predecessor subtree backwards. See Dijkstra’s 1959 paper “A Note on Two Problems in Connexion with Graphs” in Numerische Mathematik (Volume 1, pages 269-271) for more information.

Your task: given a weighted digraph D = (V, E) where the edge weights represent distances between two vertices, a starting vertex s, and a destination vertex f, use Dijkstra’s Algorithm to find the shortest path from s to f in G. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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