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.

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 616 other followers

%d bloggers like this: