From: Samuel Sol <samuel.sol@gmail.com>
Reply-To: Lua list <lua@bazar2.conectiva.com.br>
To: Lua list <lua@bazar2.conectiva.com.br>
Subject: Re: Implementing the Dijkstra Algorithm
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 <http://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>
>