【图论实战】 Boost学习 03：dijkstra_shortest_paths

示例

最短路径: A -> C -> D -> F -> E -> G 长度 16

代码

#include <iostream> 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/properties.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/named_function_params.hpp>
#include <vector>
#include <string>
using namespace std;
using namespace boost;struct Node{string id_;
};
struct EdgeProperty{int id_;int weight_;EdgeProperty(int id,int weight){id_=id;weight_=weight;}
};
typedef boost::adjacency_list < boost::listS, boost::vecS, boost::undirectedS, Node, boost::property <boost::edge_weight_t, unsigned long>> graph_t;
typedef boost::graph_traits <graph_t>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits <graph_t>::edge_descriptor edge_descriptor;
enum {A, B, C, D, E, F,G };
string vtx[]={"A","B","C","D","E","F","G"};/* 获取路径经过结点的信息 */
void GetPath(int fromId,int toId,vector<vertex_descriptor>& vPredecessor,std::string& strPath){vector<int> vecPath;while(fromId!=toId){vecPath.push_back(toId);//因为本例子的特殊性和自己很懒,所以可以直接取值toId = vPredecessor[toId];}vecPath.push_back(toId);	vector<int>::reverse_iterator pIter = vecPath.rbegin();strPath="路径:";std::string strOperator="->";string c[20]={};for(;pIter!=vecPath.rend();pIter++){// sprintf(c,"%c",vtx[*pIter]);if(*pIter!=fromId){strPath+=(strOperator+vtx[*pIter]);}else{strPath+=vtx[*pIter];}}
}int main()
{/* modify vertex */graph_t g(7);for(int i=0;i< boost::num_vertices(g); i++){g[i].id_=vtx[i];}/* modify edge and weight */typedef std::pair<int, int> Edge;	boost::property_map<graph_t,edge_weight_t>::type weightmap= get(boost::edge_weight_t(), g);Edge edge_array[] = { Edge(A,B), Edge(A,C), Edge(B,C), Edge(B,D),Edge(B,E),Edge(C,D), Edge(D,F), Edge(E,F),Edge(E,G),Edge(F,G)};int weight[]={2,5,4,6,10,2,1,3,5,9};						  int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);					for (int i = 0; i < num_edges; ++i){auto ed=add_edge(edge_array[i].first, edge_array[i].second, g);boost::put(boost::edge_weight_t(), g, ed.first,weight[i]);}/* 路径计算结果定义*///存储从起始结点到其他结点的路径上经过的最后一个中间结点序号vector<vertex_descriptor> vPredecessor(boost::num_vertices(g));//存储起始结点到其他结点的路径的距离vector<unsigned long> vDistance(boost::num_vertices(g)); /*路径探索起始点定义*/vertex_descriptor s = boost::vertex(0, g); boost::property_map<graph_t, boost::vertex_index_t>::type pmpIndexmap = boost::get(boost::vertex_index, g);boost::dijkstra_shortest_paths(g, // IN: 图s, // IN: 起始点&vPredecessor[0], // OUT：存储从起始结点到其他结点的路径上经过的最后一个中间结点序号&vDistance[0], 	 // UTIL/OUT：存储起始结点到其他结点的路径的距离weightmap, 	 	 // IN： 权重矩阵pmpIndexmap,		 // IN：std::less<unsigned long>(), // IN: 对比函数boost::closed_plus<unsigned long>(), // IN： 用来计算路径距离的混合函数std::numeric_limits<unsigned long>::max(), // IN: 距离最大值 0, boost::default_dijkstra_visitor()); // OUT:指定每个点所运行的动作std::string strPath;GetPath(0,6,vPredecessor,strPath);cout<<strPath<<endl;cout<<"路径长度:"<<vDistance[6]<<endl;boost::dynamic_properties dp;dp.property("node_id", get(boost::vertex_index, g));dp.property("label",  get(boost::edge_weight,  g));ofstream outf("min.gv");write_graphviz_dp(outf, g,dp);return 0;
}

// named parameter version
template <typename Graph, typename P, typename T, typename R>
void dijkstra_shortest_paths(Graph& g,typename graph_traits<Graph>::vertex_descriptor s,const bgl_named_params<P, T, R>& params);// non-named parameter version
template <typename Graph, typename DijkstraVisitor, typename PredecessorMap, typename DistanceMap,typename WeightMap, typename VertexIndexMap, typename CompareFunction, typename CombineFunction, typename DistInf, typename DistZero, typename ColorMap = default>
void dijkstra_shortest_paths(const Graph& g,typename graph_traits<Graph>::vertex_descriptor s, PredecessorMap predecessor, DistanceMap distance, WeightMap weight, VertexIndexMap index_map,CompareFunction compare, CombineFunction combine, DistInf inf, DistZero zero,DijkstraVisitor vis, ColorMap color = default)// version that does not initialize the property maps (except for the default color map)
template <class Graph, class DijkstraVisitor,class PredecessorMap, class DistanceMap,class WeightMap, class IndexMap, class Compare, class Combine,class DistZero, class ColorMap>
void dijkstra_shortest_paths_no_init(const Graph& g,typename graph_traits<Graph>::vertex_descriptor s,PredecessorMap predecessor, DistanceMap distance, WeightMap weight,IndexMap index_map,Compare compare, Combine combine, DistZero zero,DijkstraVisitor vis, ColorMap color = default);