Programming Practice: Dijkstra's Algorithm

dijkstra.cpp

// this version does not use a priority queue
 
#include <iostream>
 
int main() { 
 
    const int N = 9;     // number of nodes
    const int start = 0; // source
    const int goal = 4;  // destination
 
    // data
    int A[N][N] = {{ 0,  4, -1, -1, -1, -1, -1,  8, -1},
                   { 4,  0,  8, -1, -1, -1, -1, 11, -1},
                   {-1,  8,  0,  7, -1,  4, -1, -1,  2},
                   {-1, -1,  7,  0,  9, 14, -1, -1, -1},
                   {-1, -1, -1,  9,  0, 10, -1, -1, -1},
                   {-1, -1,  4, 14, 10,  0,  2, -1, -1},
                   {-1, -1, -1, -1, -1,  2,  0,  1,  6},
                   { 8, 11, -1, -1, -1, -1,  1,  0,  7},
                   {-1, -1,  2, -1, -1, -1,  6,  7,  0}};
        
    int visited[N]; // visited
    int dist[N]; // shortest distance from source to node n
    int pred[N]; // the pred. of node n on the shortest path to n
 
    // initialize matrices
    for(int i = 0; i<N; ++i) {
        visited[i] = false;
        dist[i] = std::numeric_limits<int>::max();
        pred[i] = -1;
    }
    dist[start] = 0;
 
    while(true) {
 
        // search for p, the closest unvisited node
        int p = -1;
        int p_dist = std::numeric_limits<int>::max();
        for(int i = 0; i < N; ++i) {
            if(!visited[i] && dist[i] < p_dist) {
                p_dist = dist[i];
                p = i;
            }
        }
        if (p == -1)
            break;
 
        // visit p
        visited[p] = true;
 
        // for each unvisited child c of p
        // we update shortest path dist to c if we find a shorter one.
        for(int c = 0; c < N; ++c) {
            int edge_len = A[p][c];
            if(edge_len > 0 && !visited[c]) {
                int c_dist =  p_dist + edge_len;
                if(c_dist < dist[c]) {
                    dist[c] = c_dist;
                    pred[c] = p;
                }
            }
        }
    }
 
   
    // print path
    int stack[N];
    int stack_top = -1;
    int t = goal;
    while(t >= 0) {
        stack[++stack_top] = t;
        t = pred[t];
    }
    std::cout << "shortest path: ";
    while(stack_top >= 0) 
        std::cout << stack[stack_top--] << " ";
    std::cout << std::endl;
 
    return 0;
} 

dijkstra_priorityq.cpp

// this version does not use a priority queue
 
#include <iostream>
#include <limits>
#include <queue>
 
struct node {
    int id;
    int dist;
    node(int i, int d) : id(i), dist(d) {}
    bool operator<(const node & o) const {
        return dist > o.dist;
    }
};

int main() { 
 
    const int N = 9;     // number of nodes
    const int start = 0; // source
    const int goal = 4;  // destination
 
    // data
    int A[N][N] = {{ 0,  4, -1, -1, -1, -1, -1,  8, -1},
                   { 4,  0,  8, -1, -1, -1, -1, 11, -1},
                   {-1,  8,  0,  7, -1,  4, -1, -1,  2},
                   {-1, -1,  7,  0,  9, 14, -1, -1, -1},
                   {-1, -1, -1,  9,  0, 10, -1, -1, -1},
                   {-1, -1,  4, 14, 10,  0,  2, -1, -1},
                   {-1, -1, -1, -1, -1,  2,  0,  1,  6},
                   { 8, 11, -1, -1, -1, -1,  1,  0,  7},
                   {-1, -1,  2, -1, -1, -1,  6,  7,  0}};
        
    bool visited[N]; // visited
    int dist[N]; // distance of shortest path so far from source.
    int pred[N]; // the pred. of node n on the shortest path to n
 
    // initialize matrices
    for(int i = 0; i<N; ++i) {
        visited[i] = false;
        dist[i] = std::numeric_limits<int>::max();
        pred[i] = -1;
    }

    std::priority_queue<node> q;

    // insert first node
    q.push(node(start, 0));

    while(!q.empty()) {
 
        // get the closest unvisited node.
        node u = q.top();
        q.pop();
 
        // visit t
        visited[u.id] = true;
 
        // for each unvisited child v
        for(int v = 0; v < N; ++v) {
            int w = A[u.id][v];
            if(w > 0 && !visited[v]) {
               int vdist = u.dist + w;
               if(vdist < dist[v]) {
                    dist[v] = vdist;
                    pred[v] = u.id;
                    q.push(node(v, vdist));
               }
            }
        }
    }
 
    // print path
    int stack[N];
    int stack_top = -1;
    int t = goal;
    while(t >= 0) {
        stack[++stack_top] = t;
        t = pred[t];
    }
    std::cout << "shortest path: ";
    while(stack_top >= 0) 
        std::cout << stack[stack_top--] << " ";
    std::cout << std::endl;
 
    return 0;
}