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