Dijkstra`s algorithm for shortest path

[KraHen]

I had this laying around from 10th grade lol, releasing random codes now.

So what is Dijkstra`s algorithm? It calculates the shortest path from one node to all the other nodes in a weighted graph. For node-to-node paths use the A* algorithm instead, if you need the path from every node to every node, use Roy-Floyd or Floyd-Warshall algorithm.

The code reads a weighted graph from a file format that looks like this...

NUMBER_OF_NODES
edgelength(0,0) edgelength(0,1) ... edgelength(0,n)
...
edgelength(n,0) ... edgelength(n,n)

edgelength(x,y) equals the length of the edge if there is an edge between the nodes, and 0 if there isn`t an edge (or x=y)

Here`s a video of how it works:

(Don`t mind the simple code, this was done aaaaaaaaages ago)

 Spoiler

PHP Code:

#include <iostream>
#include <queue>
#include <fstream>

#define MAX 100

using namespace std;

struct Data
{
    int N;
    int graph[MAX][MAX];
    int d[MAX];
    int father[MAX];
    bool marked[MAX];
};

void getData(Data & data)
{
    ifstream fin("graph.txt");
    fin >> data.N;
    for(int i=0; i<data.N; ++i)
    {
        for(int j=0; j<data.N; ++j)
        {
            fin >> data.graph[i][j];
        }
    }
    fin.close();
}

void dijkstra(int start, Data & data)
{
    priority_queue<pair<int,int> > q;
    pair<int, int> node;
    for(int i=0; i<data.N; ++i)
    {
        data.d[i] = 9999999; // distance = infinity, we cant see the node
        data.father[i] = -1; // we didnt come here from anywhere...
        data.marked[i] = false; // we didnt visit this node
    }

    data.d[start] = 0;
    q.push(pair<int,int> (data.d[start], start));
    while(!q.empty())
    {
        node = q.top(); // nem q.front, de miert? o.o
        q.pop();
        int i = node.second;
        if(!data.marked[i])
        {
            data.marked[i] = true;
            for(int j=0; j<data.N; ++j)
            {
                if(!data.marked[j] && data.graph[i][j] > 0 && data.d[i] + data.graph[i][j] < data.d[j])
                {
                    data.d[j] = data.d[i] + data.graph[i][j];
                    data.father[j] = i;
                    q.push(pair<int, int>(-data.d[j], j));
                }
            }
        }
    }
}

void printPath(int end, Data & data)
{
    cout << end+1 << ' ';
    while (data.father[end]!= -1)
    {
        cout << data.father[end]+1 << " ";
        end = data.father[end];
    }
    cout << endl;
}

int main()
{
    Data data;
    getData(data);
    cout << "Start = ";
    int start; cin >> start;
    start--;
    dijkstra(start, data);
    for(int i=0; i<data.N; ++i)
    {
        if(i!=start)
        {
            cout << "Path from " << i+1 << " to " << start+1 << ": ";
            printPath(i, data);
        }
    }
    cin.get();
    cin.get();
    return 0;
} 


[Xio.]

Re-Implemented in C#. Was kinda slow so I had to stackalloc the array.

Using it for Co2 pathfinding from A to B on the same map (not mobs, more like a GPS) and it completes from Warehouse man to Mine Teleporter in 161ms (Twin City) I'm satisfied. It also appears to be very close to the Pathfinding algo used in the client. It's almost always aligned. I'm spawning squamas on each node so I can compare that

[werdi9]

I program in C ++ so it can help you something?

[KraHen]

Originally Posted by Xio.

Re-Implemented in C#. Was kinda slow so I had to stackalloc the array.

Using it for Co2 pathfinding from A to B on the same map (not mobs, more like a GPS) and it completes from Warehouse man to Mine Teleporter in 161ms (Twin City) I'm satisfied. It also appears to be very close to the Pathfinding algo used in the client. It's almost always aligned. I'm spawning squamas on each node so I can compare that

I think that it would be way better if you used this for map-to-map travels (the nodes being the maps), and on the same map A* would probably yield better results. Then again, I`m happy if you`re happy with the results.

[Xio.]

Originally Posted by KraHen

I think that it would be way better if you used this for map-to-map travels (the nodes being the maps), and on the same map A* would probably yield better results. Then again, I`m happy if you`re happy with the results.

I used A* before, it's faster for short paths but it tends to have too much "noise" in it.. I don't know if that made sense..

Lets say the path is like

Start-------------------------End (a straight line)

A* would end up having useless 1 node turns in it like:

Start--------___-----_-----------_---End

While Dijkstra does exactly what it should. A straight line:

Start-------------------------End

If i play around with the cost and heuristics it ends up being way slower than Dijkstra's approach in many cases. A* is faster for < 35 nodes but since I expect a min. of 80 nodes for my case of use, I'll stick with Dijkstra for now


Thanks for your suggestion though! <3

[KraHen]

Well, yes, A* is a heuristic search, hence it won`t always yield the absolute very best, but a close approximation, putting more focus on efficiency. Also, is that a problem? I mean you have to split that path in jump points anyway, so does it really matter? Or are you using it for walk/run only (ex. mobs)?

A* will also produce a straight line if you implement tie-breaking.

[Xio.]

Originally Posted by KraHen

Well, yes, A* is a heuristic search, hence it won`t always yield the absolute very best, but a close approximation, putting more focus on efficiency. Also, is that a problem? I mean you have to split that path in jump points anyway, so does it really matter? Or are you using it for walk/run only (ex. mobs)?

I'm using it to display every step they need to take. It will put a squama on every tile thats in the path. It's used for more complex quests where they have to talk to npcs that may be really far away or on different maps, so it shows them the way. Conquer GPS basically