BGL使用dijkstra计算图的最短路径

BGL(Boost Graph Library )是 C++中著名的准标准库Boost中关于图论库，内置了常用的图论算法如BFS、DFS、dijkstra等，可以很方便的使用。
使用Boost首先需要对Boost进行配置，关于Boost的配置的文章有许多，配置起来还是非常容易的。

Boost Graph Library（BGL）是C++ Boost库的成员之一。Boost是一个经过千锤百炼的C++库，作为标准模板库STL的后备，是C++标准化进程的发动机之一。Boost库由C++标准委员会库工作组成员发起，在C++社区中影响甚大，是不折不扣的“准”标准库。
BGL的特点是灵活性和高运行效率。BGL是以模板的形式提供的，这意味着你可以在模板的基础上创建自己的类型，比如自定义的节点类。BGL的开发者是世界上最顶尖的C++专家，这个库中实现的各种图算法具有非常高的执行效率，而且BGL本身具有工业强度，你可以放心的使用它。此外，BGL的代码结构良好，是非常值得研读的精品，对于学习算法与数据结构会有很大的帮助。
从我的角度来看，BGL的缺点是没有提供复杂网络分析的算法，所以在实际中我使用的还不多。建议对于分析大规模的网络问题时使用这个库，利用它良好的图数据结构，开发自己的复杂网络分析算法，将会获得很高的执行效率。
介绍几个图论和复杂网络的程序库

问题简述：
计算路径的所用的图

起始点为A，终止点为F
求最短路径

代码如下：

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <utility>                   // for std::pair
#include <algorithm>                 // for std::for_each
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

using namespace boost;
using namespace std;


int main(int, char*[])
{
    // create a typedef for the Graph type
    typedef property<edge_weight_t, int> EdgeWeightProperty; //边的权重
    typedef adjacency_list<vecS, vecS, directedS,no_property,EdgeWeightProperty> Graph;
    typedef graph_traits < Graph >::vertex_descriptor vertex_descriptor;
    typedef std::pair<int, int> Edge;
    enum {A,B,C,D,E,F,G,N};


    Graph mygraph;
    add_edge(A, B, 6, mygraph);
    add_edge(B, C, 6, mygraph);
    add_edge(B,D ,3 , mygraph);
    add_edge(D,E ,4 , mygraph);
    add_edge(D, F, 2, mygraph);
    add_edge(E,F ,4 , mygraph);
    add_edge(C, F, 9, mygraph);






    int ipot_st, ipot_end;

    ipot_st  = A; //起始点
    ipot_end = F; //结束




    std::vector<vertex_descriptor> p(num_vertices(mygraph));
    std::vector<Graph::edge_descriptor> q(num_vertices(mygraph));
    std::vector<int> d(num_vertices(mygraph));
    vertex_descriptor s = vertex(ipot_st, mygraph);
    std::cout << " start point Vertext A to F" << std::endl;
    dijkstra_shortest_paths(mygraph, s,
        predecessor_map(boost::make_iterator_property_map(p.begin(), get(boost::vertex_index, mygraph))).
        distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, mygraph))));

    std::cout << "distances and parents:" << std::endl;
    graph_traits < Graph >::vertex_iterator vi, vend;


  //输出从A点 到其余点的最短距离和父节点
    for (boost::tie(vi, vend) = vertices(mygraph); vi != vend; ++vi) {
        std::cout << "distance(" << *vi << ") = " << d[*vi] << ", ";
        std::cout << "parent(" << *vi << ") = " << p[*vi] << std::
            endl;
    }

    //从终止点到起始点的路径
    int t = ipot_end;
    vector<int> path;
    for (; t != ipot_st; t = p[t])
        path.push_back(t);
    path.push_back(ipot_st);
    //反转路线 从起始点到出发点
    reverse(path.begin(), path.end());

    //输出路径
    for (int i =0;i<path.size();i++)
    {
        std::cout << path[i] << "->" << std::endl;
    }


    system("pause");
    return 0;
}

路线点为
0 -> 1 -> 3 ->5
即为： A->B->D->F