lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

On a side note, as also suggested on that wikipedia page, and depending on what exactly you are using the algorithm for, you might want to consider using the A* algorithm instead. Or perhaps another variant dubbed the D* algorithm, where the shortest path found can be dynamically updated "en-route" in real-time (i.e. while actually travelling) as circumstances might change over time. I found a research paper about this once, I could email it to you if you like, just let me know. The algorithm was designed to be implemented on robots for navigation, and I'm sure it could be useful for other applications as well, such as games and simulations. 



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>
>