Apply Dijstra on a weighted graph.

apply_dijkstra.cpp

#include <iostream>
#include <utility> 
#include <vector>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

using namespace boost;

using std::pair;
using std::vector;
using std::cout;
using std::endl;

int main()
{
    // The edges will be weighted with int values
    typedef adjacency_list<vecS, vecS, directedS,
        no_property, property<edge_weight_t, int>> Graph;
    typedef graph_traits<Graph>::vertex_descriptor V;
    
    // Make convenient labels for the vertices
    enum { _1, _2, _3, _4, _5, _6, N };
    const int num_nodes = N;
    const char* name = "CLRS_22.4";
    
    // writing out the edges in the graph
    typedef pair<int, int> Edge;
    Edge edge_array[] = { 
        Edge(_1,_2), Edge(_1,_4),
        Edge(_2,_3), Edge(_2,_5),
        Edge(_3,_5), Edge(_3,_6), 
        Edge(_4,_2),
        Edge(_5,_4),
        Edge(_6,_6)
    };
    const int num_edges = sizeof(edge_array)/sizeof(Edge);
    int weights[] = { 1, 6, 2, 1, 3, 2, 0, 1, 0 };
    Graph g(edge_array, edge_array + num_edges, weights, num_nodes);
    
    // Vector that will hold Dijkstra's results
    vector<int> distances(num_vertices(g));
    
    V start = *(vertices(g).first);
    dijkstra_shortest_paths(g, start, distance_map(&distances[0]));
    
    // Print the result
    cout << "distances from start vertex:" << endl;
    typedef property_map<Graph, vertex_index_t>::type IndexMap;
    IndexMap index = get(vertex_index, g);
    graph_traits<Graph>::vertex_iterator vi;
    for (vi = vertices(g).first; vi != vertices(g).second; ++vi)
        cout << "distance(" << (index(*vi) + 1) << ") = " << distances[*vi] << endl;
    cout << endl;
}