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.

About these ads

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 [...]

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 609 other followers

%d bloggers like this: