Dijkstra's Algorithm - in C++

dijkstra's algorithm - in c++?

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;
}

Need help understanding Dijkstra's Algorithm

Relax decreases the values in minQ.

The first extracted node is the source, since 0 < MAX_INT. Then, every adjacent node gets relaxed, which decreases its minQ value to 0+c, where c is the cost of the edge from source to the node, if it is lower than the current minQ value.
This is the case here, since the previous values are all INT_MAX.

Now all of the Vertices adjacent to the source have been marked with the shortest already discovered path to reach them.

Then one of the processed vertices will have the lowest minQ value, and it will be extracted and processed next.

You should now be able to see how this extracting->relaxing cycle results in a graph where each node is marked with the minimum cost to reach it.

If you update a pointer to the relaxed-from node each time a relaxation happens, you can just walk backwards from the desired target node to read the shortest path.

Why does my implementation of Dijkstra's algorithm not behave as it should?

Read Step 6 of Wikipedia's algorithm again:

Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and go back to step 3.

The "select" here means "among all the unvisited nodes in the entire graph", not just among the unvisited neighbors of the current node, which is what your code is doing. So if the unvisited node of smallest tentative distance is not a neighbor of the current node, your code goes astray. And if the current node has no unvisited neighbors at all (which is entirely possible, either with a situation like what you encountered, or more simply with a dead-end node), your code absurdly visits the local_closest node, which isn't in the graph at all and whose edges are uninitialized, naturally causing a crash.

So you diverged from the correct algorithm sooner than the visit to A which you are focusing on. When you finished visiting D, the remaining unvisited nodes were A at tentative distance 2, C at tentative distance 4, and B,F,H at tentative distance infinity. So by the algorithm, you ought to visit A next. But instead you visit C, again because your code wrongly only considers neighbors of the current node as candidates for the next node to visit.

Frankly I don't see how a recursive algorithm is going to be workable at all here. You need to have access to some data structure that tracks all the unvisited nodes, so that at any time you can find the one at minimum tentative distance, even if it's very far away from your current node. Your idea of keeping track of visited status on the nodes themselves has a problem with this, because you have no good way to search them all, except by going back to the starting node and doing some kind of DFS/BFS. That's (1) not possible in your current implementation, because the recursive calls to dijkstra no longer have a pointer to the starting node, and (2) very inefficient, because it's O(N) on every visit.

There's a good reason why the Wikipedia algorithm suggests using a set here. And I think it lends itself better to an iterative than to a recursive algorithm.

---

Related Topics