Re: Implementing the Dijkstra Algorithm

[Luis Carvalho <carvalho@...>]

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