dijkstra's algorithm - in c++?

Question

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

EDIT: Special thanks to "Loki astari" for his excellent answer

Answer 1

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 set 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 guaranteed 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 bubble always expands outwards and we always expand the part of the bubble that is smallest.

So the next step is to take the head of the list and repeat. From Southampton there are only two destinations. Back to London (which we discard as it is 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), (Birmingham,110), (Oxford, 120), (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 go to 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  = { (Birmingham,110), (Oxford, 120), (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.