dijkstrasBN.cpp

#include <iostream>
#include <cmath>
#include <set>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
#include <limits>
#include <iterator>
#include <list>
using namespace std;

typedef int vertex_t;
typedef double weight_t;

const weight_t max_weight = numeric_limits<double>::infinity();

// types
// 0 - by foot
// 1 - by bus
// 2 - by car
class neighbor {
public:
    vertex_t target;
    weight_t weight;
    vertex_t type;

    neighbor(vertex_t target_arg, weight_t weight_arg, vertex_t arg_type)
        : target(target_arg), weight(weight_arg), type(arg_type)
    {}
};

typedef vector< vector<neighbor> > adjacency_list_t;


void DijkstraCompute(int source, const adjacency_list_t &adj_list,
                     vector <weight_t> &min_distance,
                     vector <vertex_t> &previous,
                     vector <vertex_t> &prev_type)
{

    int n = adj_list.size();

    std::set <std::pair <weight_t, vertex_t> > vertex_queue;

    min_distance.clear();
    min_distance.resize(n, max_weight);
    min_distance[source] = 0;

    previous.clear();
    previous.resize(n, -1);

    prev_type.clear();
    prev_type.resize(n, -1);

    vertex_queue.insert(std::make_pair(min_distance[source], source));

    while (!vertex_queue.empty()) {

        vertex_t u = vertex_queue.begin()->second;
        weight_t dist = vertex_queue.begin()->first;

        vertex_queue.erase(vertex_queue.begin());

        const vector <neighbor> &neighbors = adj_list[u];
        for(vector <neighbor>::const_iterator neighbor_it = neighbors.begin();
            neighbor_it != neighbors.end(); neighbor_it++ ) {

                vertex_t x = neighbor_it->target;
                weight_t y = neighbor_it->weight;

                weight_t distance_through_node = dist + y;
                if (distance_through_node < min_distance[x]) {
                    vertex_queue.erase(std::make_pair(min_distance[x], x));

                    min_distance[x] = distance_through_node;
                    previous[x] = u;
                    prev_type[x] = neighbor_it->type;

                    vertex_queue.insert(std::make_pair(min_distance[x], x));
                }
        }
    }
}

std::list <vertex_t> printPath(vertex_t vrtx,
                               const vector <vertex_t> &prev) {

    std::list <vertex_t> path;

    for( ; vrtx != -1; vrtx = prev[vrtx]) {
        path.push_front(vrtx);
    }

    return path;
}