【图论实战】 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);

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/187488.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

rust实现quic服务端和客户端

演示如何使用 Quinn 库实现一个简单的 QUIC 客户端和服务器。QUIC 是一种基于 UDP 的协议&#xff0c;用于在互联网上进行快速和安全的通信。 在程序中&#xff0c;使用了 Rust 的标准库中的 error、net 和 sync 模块&#xff0c;以及第三方库 tokio 和 quinn。程序使用了 asy…

[工业自动化-10]:西门子S7-15xxx编程 - PLC主站 - 信号量:数字量

目录 前言&#xff1a; 一、工业现场常见信号的分类 二、IO数字量模块 2.1 概述 2.2 PLC的数字量是24V还是5V电压&#xff1f; 2.2 数字量模块的安装与接线 2.3 数字量模的注意事项 前言&#xff1a; 一、工业现场常见信号的分类 在工业自动化领域&#xff0c;常常需要使…

操作系统 | 编写内核

&#x1f308;个人主页&#xff1a;Sarapines Programmer&#x1f525; 系列专栏&#xff1a;《操作系统实验室》&#x1f516;少年有梦不应止于心动&#xff0c;更要付诸行动。 目录结构 1. 操作系统实验之编写内核 1.1 实验目的 1.2 实验内容 1.3 实验步骤 1.4 实验过程 …

VScode + opencv(cmake编译) + c++ + win配置教程

1、下载opencv 2、下载CMake 3、下载MinGW 放到一个文件夹中 并解压另外两个文件 4、cmake编译opencv 新建文件夹mingw-build 双击cmake-gui 程序会开始自动生成Makefiles等文件配置&#xff0c;需要耐心等待一段时间。 简单总结下&#xff1a;finish->configuring …

轻量日志管理方案-[EFK]

使用FileBeat进行日志文件的数据收集&#xff0c;并发送到ES进行存储&#xff0c;最后Kibana进行查看展示&#xff1b; 这个应该是最简单&#xff0c;轻量的日志收集方案了。 最总方案为&#xff1a;FileBeatESKibana ; 【Kibana过于强大&#xff0c;感觉可以无限扩展】 文章目…

边缘计算多角色智能计量插座:用电监测和资产管理的未来智能化引擎

目前主流的智能插座涵盖了红外遥控&#xff08;控制空调和电视等带有红外标准的电器&#xff09;&#xff0c;配备着测温、测湿等仓库应用场景&#xff0c;配备了人体红外或者毫米波雷达作为联动控制&#xff0c;但是大家有没有思考一个问题&#xff0c;就是随着对接的深入&…

django|报错SQLite 3.8.3 or later is required的解决方案

迁移原同事写的程序&#xff0c;到新服务器上边。运行报错。解决方案有三种 降低django版本升级sqlite3&#xff0c;不低于3.8.3版本修改django源码 方案一、降低django版本 卸载高版本django pip uninstall django安装低版本&#xff0c;如 pip install django2.1.7注意&…

汽车标定技术(八)--MPC57xx是如何支持标定的页切换

目录 1.页切换的概念 1.1 标定常量的理解 1.2 页切换 2.MPC57xx的Overlay模块 3.小结 1.页切换的概念 在汽车标定测量中&#xff0c;有一个概念我想很多人都听过&#xff0c;但是实际上在项目里没有用到过&#xff0c;那就是今天要讲的页切换概念。在讲页切换的时候&#…

python注释(快捷键)

首先介绍以下三种注释方式&#xff1a; # 123&#xff08;单行注释&#xff09; """123"""&#xff08;多行注释&#xff09; 123&#xff08;多行注释&#xff09; 下面介绍一下快捷键&#xff1a; Ctrl/ 注释单行&#xff1a;指针只要在这行代…

Arcgis连接Postgis数据库(Postgre入门十)

效果 步骤 1、矢量数据首先有在postgis数据库中 这个postgis数据库中的一个空间数据&#xff0c;数据库名称是test3&#xff0c;数据表名称是test 2、Arcgis中连接postgis数据库中 3、成功连接 可以将数据拷贝或导入到gdb数据库中

图数据库Neo4j详解

文章目录 第一章 图和Neo4j1.1 图数据库概念1.1.1 图论起源1.1.2 节点-关系及图1.1.3 图数据库1.1.4 图数据库分类1.1.4 图数据库应用场景1.1.5 与关系型数据库对比1.1.6 图数据库优势 1.2 Neo4j介绍1.2.1 Neo4j是什么1.2.2 Neo4j特点1.2.3 Neo4j的优势1.2.4 Neo4j的限制1.2.5 …

机器学习——实践

目录 一、数据集划分 1、交叉验证 2、不平衡数据的处理 代价敏感学习 二、评价指标 三、正则化、偏差和方差 为什么要标准化/归一化&#xff1f; 过拟合的处理——Dropout 过拟合的处理——Early stopping 过拟合的处理——数据增强 偏差和方差 ​编辑 一、数据集划分…

机器学习——奇异值分解案例(图片压缩-代码简洁版)

本想大迈步进入前馈神经网络 但是…唉…瞅了几眼&#xff0c;头晕 然后想到之前梳理的奇异值分解、主成分分析、CBOW都没有实战 如果没有实际操作&#xff0c;会有一种浮在云端的虚无感 但是如果要实际操作&#xff0c;我又不想直接调用库包 可是…如果不直接调包&#xff0c;感…

【计算机网络笔记】Internet网络的网络层——IP协议之IP数据报的结构

系列文章目录 什么是计算机网络&#xff1f; 什么是网络协议&#xff1f; 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能&#xff08;1&#xff09;——速率、带宽、延迟 计算机网络性能&#xff08;2&#xff09;…

Pytorch实战教程(一)-神经网络与模型训练

0. 前言 人工神经网络 (Artificial Neural Network, ANN) 是一种监督学习算法,其灵感来自人类大脑的运作方式。类似于人脑中神经元连接和激活的方式,神经网络接受输入,通过某些函数在网络中进行传递,导致某些后续神经元被激活,从而产生输出。函数越复杂,网络对于输入的数…

离线视频ocr识别

sudo apt-get install libleptonica-dev libtesseract-dev sudo apt-get install tesseract-ocr-chi-sim python -m pip install video-ocrwindows安装方法&#xff1a; 下载安装 https://digi.bib.uni-mannheim.de/tesseract/tesseract-ocr-w64-setup-5.3.3.20231005.exe 下…

百度智能云千帆大模型平台再升级,SDK版本开源发布!

文章目录 1. SDK的优势2. 千帆SDK&#xff1a;快速落地LLM应用3. 如何快速上手千帆SDK3.1 SDK快速启动3.2 SDK进阶指引3.3 通过Langchain接入千帆SDK 4. 开源社区 百度智能云千帆大模型平台再次升级&#xff01;在原有API基础上&#xff0c;百度智能云正式上线Python SDK&#…

nodejs express vue 酒店预订系统源码

开发环境及工具&#xff1a; nodejs&#xff0c;vscode&#xff08;webstorm&#xff09;&#xff0c;大于mysql5.5 技术说明&#xff1a; nodejs express vue elementui 功能介绍&#xff1a; 用户端&#xff1a; 用户登录注册 首页显示轮播图&#xff0c;客房分类&…

【媒体邀约】媒体宣传——企业成长的催化剂

传媒如春雨&#xff0c;润物细无声&#xff0c;大家好&#xff0c;我是51媒体网胡老师。 媒体宣传是企业成长的催化剂&#xff0c;它在各种方面对企业的成功和发展起到了关键作用。 1. 曝光和知名度&#xff1a; 媒体宣传可以将企业和其产品或服务推向广泛的受众&#xff0c;…

通义千问, 文心一言, ChatGLM, GPT-4, Llama2, DevOps 能力评测

引言 “克隆 dev 环境到 test 环境&#xff0c;等所有服务运行正常之后&#xff0c;把访问地址告诉我”&#xff0c;“检查所有项目&#xff0c;告诉我有哪些服务不正常&#xff0c;给出异常原因和修复建议”&#xff0c;在过去的工程师生涯中&#xff0c;也曾幻想过能够通过这…