• Subject: Re: Implementing the Dijkstra Algorithm
• From: Samuel Sol <samuel.sol@...>
• Date: Tue, 22 Nov 2005 13:19:48 -0200

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>