lua-users home
lua-l archive

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


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