[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Implementing the Dijkstra Algorithm
- From: Samuel Sol <samuel.sol@...>
- Date: Mon, 21 Nov 2005 16:59:07 -0200
Hello my friends,
I've been fooled by Dijkstra Algorithm by 2 weeks at least
now, so I'm coming to you asking for help to solve this problem.
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.
I put a .zip file at
http://www.castelodelego.org/sol/locationsdata.zip that you can get all
the files I use for this program.
--- Explain the Data ---
The graph is represented by a numeric table with the following characteristics:
graph ={
[key1] = {
[conection1_key] = {cost1},
[conection2_key] = {cost2},
...
},
[key2] = {
[conection1_key] = {cost1},
[conection2_key] = {cost2},
...
},
...
}
All costs are non-negative, so the Dijkstra can be implemented. The infinity distance is defined by a constant:
infinite = 1000000000; -- this number was choosen because no path can have a cost like this.
The function find_shortest_path should return a table with
the nodes to make the path with the first element been the start and
the last the finish:
returner = {
[1] = {start},
[2] = {node 1},
...
[n] = {finish},
}
After the while on line ___ is executed, the table "d"
will contain the distance value from the start point to every point in
the graph. The table "previous", will be filled with the previous
element on the path from the start node to that particular node.
The graphs I'm using as example are connected. So there is
a path from each point to every other one. They will be used on the
real implementation of the program (a World of Warcraft add-on).
Hope you guys can help me
Sol