Dijkstra's Algorithm in C++

Dijkstra's Algorithm

Dijkstra's algorithm is a single source shortest path (sssp) algorithm. Like BFS, this famous graph searching algorithm is widely used in programming and problem solving, generally used to determine shortest tour in a weighted graph. This algorithm is almost similar to standard BFS, but instead of using a Queue data structure, it uses a heap like data structure or a priority queue to maintain the weight order of nodes. Here is the algorithm and pseudo-code. You can also look into Introduction to Algorithms (by C.L.R.S).

Here is a short implementation of this algorithm in C++, I assumed that, all the edge-weights are positive, and the max possible distance is less than 2²⁰ which is set as INF. The nodes are marked from 1 to N inclusive where N is the number of nodes.

Input format:

N E // number of nodes and edges
E lines containing an edge (u, v, w) on each line // edge(u, v, w) means weight of edge u-v is w. Nodes u, v are within range 1 to N
S // starting node

C++ code:

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

#define MAX 100001
#define INF (1<<20)
#define pii pair< int, int >
#define pb(x) push_back(x)

struct comp {
    bool operator() (const pii &a, const pii &b) {
        return a.second > b.second;
    }
};

priority_queue< pii, vector< pii >, comp > Q;
vector< pii > G[MAX];
int D[MAX];
bool F[MAX];

int main() {
    int i, u, v, w, sz, nodes, edges, starting;

    // create graph
    scanf("%d %d", &nodes, &edges);
    for(i=0; i<edges; i++) {
        scanf("%d %d %d", &u, &v, &w);
        G[u].pb(pii(v, w));
        G[v].pb(pii(u, w)); // for undirected
    }
    scanf("%d", &starting);

    // initialize distance vector
    for(i=1; i<=nodes; i++) D[i] = INF;
    D[starting] = 0;
    Q.push(pii(starting, 0));

    // dijkstra
    while(!Q.empty()) {
        u = Q.top().first;
        Q.pop();
        if(F[u]) continue;
        sz = G[u].size();
        for(i=0; i<sz; i++) {
            v = G[u][i].first;
            w = G[u][i].second;
            if(!F[v] && D[u]+w < D[v]) {
                D[v] = D[u] + w;
                Q.push(pii(v, D[v]));
            }
        }
        F[u] = 1; // done with u
    }

    // result
    for(i=1; i<=nodes; i++) printf("Node %d, min weight = %d\n", i, D[i]);
    return 0;
}

This is a straight forward implementation, according to the problem solving purpose, changes are to be made here and there.

Here is another implementation that does not use a custom comparison structure and the code is a bit more re-usable too. Note, that, nodes are numbered from 1 to n, pair for priority queue elements are assumed to be (weight, node) where pair for graph edges are assumed to be (node, weight). Also I have added comments to make the code more readable. Visit this codepad url for uncommented version of the code.

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

typedef pair< int, int > pii;

/*
Set MAX according to the number of nodes in the graph. Remember,
nodes are numbered from 1 to N. Set INF according to what is the
maximum possible shortest path length going to be in the graph.
This value should match with the default values for d[] array.
*/
const int MAX = 1024;
const int INF = 0x3f3f3f3f;

/*
pair object for graph is assumed to be (node, weight). d[] array
holds the shortest path from the source. It contains INF if not
reachable from the source.
*/
vector< pii > G[MAX];
int d[MAX];

/*
The dijkstra routine. You can send a target node too along with
the start node.
*/
void dijkstra(int start) {
    int u, v, i, c, w;

    /*
    Instead of a custom comparator struct or class, we can use
    the default comparator class greater<T> defined in quque.h
    */
    priority_queue< pii, vector< pii >, greater< pii > > Q;

    /*
    Reset the distance array and set INF as initial value. The
    source node will have weight 0. We push (0, start) in the
    priority queue as well that denotes start node has 0 weight.
    */
    memset(d, 0x3f, sizeof d);
    Q.push(pii(0, start));
    d[start] = 0;

    /*
    As long as queue is not empty, check each adjacent node of u
    */
    while(!Q.empty()) {
        u = Q.top().second; // node
        c = Q.top().first; // node cost so far
        Q.pop(); // remove the top item.

        /*
        We have discarded the visit array as we do not need it.
        If d[u] has already a better value than the currently
        popped node from queue, discard the operation on this node.
        */
        if(d[u] < c) continue;

        /*
        In case you have a target node, check if u == target node.
        If yes you can early return d[u] at this point.
        */

        /*
        Traverse the adjacent nodes of u. Remember, for the graph,,
        the pair is assumed to be (node, weight). Can be done as
        you like of course.
        */
        for(i = 0; i < G[u].size(); i++) {
            v = G[u][i].first; // node
            w = G[u][i].second; // edge weight

            /*
            Relax only if it improves the already computed shortest
            path weight.
            */
            if(d[v] > d[u] + w) {
                d[v] = d[u] + w;
                Q.push(pii(d[v], v));
            }
        }
    }
}

int main() {
    int n, e, i, u, v, w, start;
    /*
    Read a graph with n nodes and e edges.
    */
    while(scanf("%d %d", &n, &e) == 2) {

        /*
        Reset the graph
        */
        for(i = 1; i <= n; i++) G[i].clear();

        /*
        Read all the edges. u to v with cost w
        */
        for(i = 0; i < e; i++) {
            scanf("%d %d %d", &u, &v, &w);
            G[u].push_back(pii(v, w));
            G[v].push_back(pii(u, w)); // only if bi-directional
        }

        /*
        For a start node call dijkstra.
        */
        scanf("%d", &start);

        dijkstra(start);

        /*
        Output the shortest paths from the start node.
        */
        printf("Shortest path from node %d:\n", start);
        for(i = 1; i <= n; i++) {
            if(i == start) continue;
            if(d[i] >= INF) printf("\t to node %d: unreachable\n", i);
            else printf("\t to node %d: %d\n", i, d[i]);
        }
    }
    return 0;
}

Dijkstra is a single source shortest path problem. So if you want to see the shortest path from every node, you have to call dijkstra once for each source or starting node.