Re: Implementing the Dijkstra Algorithm

[Samuel Sol <samuel.sol@...>]

   Thank you mate, I will start implementing it. The only
think that will have to be diferent is how to mark when there is no
edge between two nodes I will use -1, because 0 is a valid cost. :)

   but noneless thanks a lot.

Sol

On 11/21/05, Luis Carvalho <carvalho@dam.brown.edu> wrote:

> I used the wikipedia article on it (link:
> http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm), as a base for the
> implementation. The problem is that the code is working erract. It returns
> correctly on the paths that need only 1 step. Most of the 2 and 3 steps and
> none that needs 4 or more steps.

Quick and dirty, following your Wikipedia link:

-- test graph: if G[u][v] == 0, there is no edge between u and v
G = {
        -- 1   2   3   4   5   6
        {  0,  0, 13,  0, 16,  8 }, -- 1
        {  0,  0,  0,  6,  0, 10 }, -- 2
        { 13,  0,  0, 14,  0, 11 }, -- 3
        {  0,  6, 14,  0,  5, 17 }, -- 4
        { 16,  0,  0,  5,  0,  7 }, -- 5
        {  8, 10, 11, 17,  7,  0 }  -- 6
}

local INF = 1/0 -- not really needed

local extract_min = function(q, d)
        local m = INF
        local i = 0
        for k, v in pairs(q) do
                if d[v] < m then
                        m = d[v]
                        i = k
                end
        end
        q[i] = nil -- remove i
        return i
end

function dijkstra (graph, start)
        local n = table.getn(graph) -- #vertices
        local d = {}
        local previous = {}
        for v = 1, n do d[v] = INF end
        d[start] = 0
        local S = {}
        local Q = {}
        for v = 1, n do Q[v] = v end -- fill Q
        local nQ = n -- # elements in Q
        while nQ > 0 do
                local u = extract_min(Q, d)
                nQ = nQ - 1
                table.insert(S, u)
                for v = 1, n do
                        if G[u][v] > 0 -- edge between u and v?
                                        and d[v] > d[u] + G[u][v] then -- relax
                                d[v] = d[u] + G[u][v]
                                previous[v] = u
                        end
                end
        end
        return d, previous
end

function path (p, start)
        local i = start
        local t = { i }
        while p[i] do
                table.insert(t, 1, p[i])
                i = p[i]
        end
        return t
end


Testing:

$ lua -i dijkstra.lua
Lua 5.1 (beta)  Copyright (C) 1994-2005 Lua.org, PUC-Rio
> d,p = dijkstra(G, 1)
> table.foreach(d, print)
1       0
2       18
3       13
4       20
5       15
6       8
> table.foreach(p, print)
2       6
3       1
4       5
5       6
6       1
> for i = 1, table.getn(G) do print(i, d[i], table.concat(path(p, i), ' -> ')) end
1       0       1
2       18      1 -> 6 -> 2
3       13      1 -> 3
4       20      1 -> 6 -> 5 -> 4
5       15      1 -> 6 -> 5
6       8       1 -> 6

Needless to say, this is just a prototype: no error checking or optimizations.

Cheers,
luis.

--
A mathematician is a device for turning coffee into theorems.
        -- P. Erdos

--
Luis Carvalho
Applied Math PhD Student - Brown University
PGP Key: E820854A < carvalho@dam.brown.edu>