已解决
【图论实战】 Boost学习 03:dijkstra_shortest_paths
来自网友在路上 169869提问 提问时间:2023-11-11 11:00:53阅读次数: 69
最佳答案 问答题库698位专家为你答疑解惑
文章目录
- 示例
- 代码
示例

最短路径: 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);
查看全文
99%的人还看了
相似问题
- 【剑指offer|图解|链表】链表的中间结点 + 链表中倒数第k个结点
- 【数据结构初阶(3)】双向带头结点循环链表
- 单链表相关面试题--4.输入一个链表,输出该链表中倒数第k个结点
- 王道数据结构课后代码题p150 15.设有一棵满二叉树(所有结点值均不同),已知其先序序列为 pre,设计一个算法求其后序序列post。(c语言代码实现)
- 【数据结构】树的基本性质(计算树的总结点数与叶结点数)
- 【数据结构】树与二叉树(五):二叉树的顺序存储(初始化,插入结点,获取父节点、左右子节点等)
- NowCoder | 链表中倒数第k个结点
- 设一棵完全二叉树具有1000个结点,则此完全二叉树有()叶子结点,有()个度为2的结点。
- 11.3递归建二叉树,二叉树函数规范化输入输出,一些二叉树性质,求叶子结点与树的高度
- 二叉树第i层结点个数
猜你感兴趣
版权申明
本文"【图论实战】 Boost学习 03:dijkstra_shortest_paths":http://eshow365.cn/6-37545-0.html 内容来自互联网,请自行判断内容的正确性。如有侵权请联系我们,立即删除!
- 上一篇: Java任意视频转MP4
- 下一篇: Geotrust的企业型通配符SSL证书申请