dijkstra's algorithm - in c++ ?

Question

Hi, for the past four days I am trying to understand the dijkstra's algorithm. But I can't. I have a vector of points. From that I created a cost matrix. But I don't know how to make the dijkstra's algorithm. Sources are available in net, but I am not from Computer science background, So I can't understand them. I am trying to make a function like this

vector<int> dijkstra(costMatrix[][])
{
  ....
  ....
  return vector<int>pathPointindex
}

main()
{
    vector<Point> availablePoints;
    costMatrix[][]=createCostMatrix();
    vector<int> indexes=dijikstra(costMatrix)
    for(int i=0;i<indexes.size();i++)
       cout << "path points are " << availablePoints[indexes[i]] << endl;
}

If anybody, can you please post the code. I am not lazy. But my project already crossed the deadline one day ago. Now I lost my hope to understand the logic. Now Just I want the function. "A man in need is the angel indeed"

Answer 1

Here you can find some implementations in C, C++ and Fortran.

Answer 2

I advise you to look at TopCoder tutorial that have very pragmatic apporach. You will need to find out how STL priority queue works and make sure you don't have any negative edge weights in your graph.

Decent full implementation can be found here. You will have to add Path vector to it and implement RecoverPath method in order to get nodes on path from source to sink. To use this solution you will also need to convert your adjacency matrix to adjacency list in following way:

for (int i=0;i<nNodes;i++)
    for (int j=0;j<nNodes;j++){
        if (costMatrix[i][j] != NO_EDGE_VALUE){
            G[i].pb(make_pair(j,costMatrix[i],[j]));
        }
    }

EDIT: If your graph is dense I would advise you to use Ford Bellman algorithm is much simpler and shouldn't be much slower.

EDIT2: To calculate path you should add in the header

int P[MAX]; /*array with links to parents*/
for(i=0; i<=nodes; i++) P[i] = -1; /*magic unset value*/

// dijkstra
while(!Q.empty()) {
    ....
    if(!F[v] && D[u]+w < D[v]) {
        D[v] = D[u] + w;
        /*By setting P[v] value we will remember what is the 
          previous node on path from source */
        P[v] = u; // <-- added line
        Q.push(pii(v, D[v]));
    }
    ...
}

Then you have to add RecoverPath method (it works only when path exists)

vector<int> RecoverPath(int src, int dest){
    vector<int> path;
    int v = dest;
    while (v != src) {
        path.push_back(v);
        v = P[v];
    }
    path.push_back(src);
    std::reverse(path.begin(),path.end());
    return path;
}

Answer 3

Dijkstra’s algorithm

In English:

This is an algorithm for finding the shortest route from point A to point B.
In computing terms we simplify the route to a graph consisting of nodes and arcs. Each node represents an intermediate point while each arc connect two nodes and has a (non negative) weight representing the cost to traverse between the two nodes.

To implement the algorithm you need two lists:

• finished: A list of (node,cost) where you have computed the minimum cost to reach.
• working: A sorted list of (node,cost) that have been checked.

Algorithm:

working.addNode(Start, 0); // No cost to get to start.

for( (node, cost) = working.popHead(); node != End; (node,cost) = working.popHead())
{
    // If we have already processed this node ignore it.
    if (finished.find(node))
    {    continue;
    }

    // We have just removed a node from working.
    // Because it is the top of the list it is guranteed to be the shortest route to
    // the node. If there is another route to the node it must go through one of the
    // other nodes in the working list which means the cost to reach it will be higher
    // (because working is sorted). Thus we have found the shortest route to the node.

    // As we have found the shortest route to the node save it in finished.
    finished.addNode(node,cost);

    // For each arc leading from this node we need to find where we can get to.
    foreach(arc in node.arcs())
    {
        dest = arc.dest();
        if (NOT (finished.find(dest)))
        {
            // If the node is already in finished then we don't need to worry about it
            // as that will be the shortest route other wise calculate the cost and add
            // this new node to the working list.
            destCost = arc.cost() + cost;
            working.addNode(dest,destCost); // Note. Working is sorted list
        }
    }
} 

So if you think about this algorithm. Say you are traveling from London to Manchester.

finished = {} // empty.
working  = { (London,0) }

Using the following Costs matrix:

                  L    S    O    B    N    M    W
(L) ondon         -    50   60   100  130  -    -
(S) outhampton    50   -    70   -    -    -    -
(O) xford         60   70   -    50   -    200  -
(B) irmingham     100  -    50   -    -    80   110
(N) orwich        130  -    -    -    -    -    -
(M) anchester     -    -    200  80   -    -    80
Ne(W) castle      -    -    -    110  -    80   -

Now you take London out of the working list (as it is at the head) and place it into the finished list. Then add to the working list all the towns directly connected to London.

finished = { (London,0) }
working  = { (Southampton, 50), (Oxford, 60), (Birmingham, 100), (Norwich,130) }

Consider the towns in the working set the outer edge of a bubble that has expanded from London. The job of Dijkstra's algorithm is to keep expanding the bubble until we hit Manchester (without retracing any steps we have already taken). SO the buble always expands outwards and we always expand the part of the buble that is smallest.

So the next step is to take the head of the list and repeat. From Southhampton there are only two destinations. Back to London or Southampton (70) which we discard as they are in the finished list) and Oxford. The cost to get to Oxford is 50 + the cost from Southampton to Oxford (so notice it is in the working list twice but don;t worry we will discard it later as not an optimal route).

finished = { (London,0), (Southampton,50) }
working  = { (Oxford, 60), (Birmingham, 100), (Oxford, 120), (Norwich,130) }

So repeat the loop. The head of the list is Oxford. From Oxford we can go to Manchester(200), Birmingham(50) or back to London(60) or Southampton(. Remember we need to add the cost of getting to oxford to each of these costs above. Note that from Oxford we could have gone to Southampton but we have already found the shortest route to Southampton so no processing is required) This will leave us with:

finished = { (London,0), (Southampton,50), (Oxford, 60) }
working  = { (Birmingham, 100), (Oxford, 120), (Birmingham,110), (Norwich,130), (Manchester,200)}

Notice we have Manchester in the working list now (this is our destination). But we need to keep working as we may find a shorter route. So now we expand from Birmingham. From there we can goto Oxford(50), Manchester(80), London(100), Newcastle(110). Adding the cost of getting to Birmingham in the first place this gives us:

finished = { (London,0), (Southampton,50), (Oxford, 60), (Birmingham, 100) }
working  = { (Oxford, 120), (Birmingham,110), (Norwich,130), {Manchester, 180), (Manchester,200), (Newcastle, 210)}

The next two nodes. Oxford and Birmingham are already in the finished list so we can ignore them. So unless there is a route from Norwich to Manchester that is less than 50 miles we will reach Manchester in the iteration after that.

Answer 4

Implementation in c ++

#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
using namespace std;

#define pb push_back
#define mp make_pair
#define MAXN 50100
#define INF 1000000000

int N, M, d[MAXN]; vector<int> G[MAXN], C[MAXN];
set< pair<int, int> > T;

void solve(void)
{
    int i, j, k, val, x;

    for(i = 2; i <= N; i++) d[i] = INF;
    T.insert( mp(0, 1) );

    while( T.size() > 0 )
    {
        val = (*T.begin()).first, x = (*T.begin()).second;
        T.erase(*T.begin());
        for(i = 0; i < G[x].size(); i++)
         if(d[ G[x][i] ] > val + C[x][i] )
            d[ G[x][i] ] = val + C[x][i], T.insert(mp(d[G[x][i]],G[x][i]));
    }
}

int main(void)
{
    freopen("dijkstra.in", "rt", stdin);
    freopen("dijkstra.out", "wt", stdout);

    int i, a, b, c;

    scanf("%d %d\n", &N, &M);

    for(i = 1; i <= M; i++)
        scanf("%d %d %d\n", &a, &b, &c), G[a].pb(b), C[a].pb(c);

    solve();

    for(i = 2; i <= N; i++)
        printf("%d ", d[i] == INF ? 0 : d[i]);

    return 0;
}