jjzjj

c++ - Boost的Dijkstra算法教程

coder 2024-02-01 原文

我很难弄清楚如何使用 Boost 的 Dijkstra 算法。我已经查看了他们的示例和文档，但我仍然无法理解如何使用它。

[Boost 的文档:http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/dijkstra_shortest_paths.html] [Dijkstra 的例子:http://www.boost.org/doc/libs/1_36_0/libs/graph/example/dijkstra-example.cpp]

有人可以提供带有代码示例的分步说明来说明如何使用 Boost 的 Dijkstra 算法吗？ 我正在为我的图表使用 Boost 的 adjacency_list，就像上面的示例链接一样。 (邻接列表:http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/adjacency_list.html)

最佳答案

关于评论中的问题:

  1. 根据示例源代码中的注释，VC++ 对 named parameter mechanism used 有一些问题。 .因此，我假设这两个分支的想法基本相同，只是 VC++ 版本更冗长(尽管我没有深入研究它足够长的时间以确保 100% 确定)。
  2. property_map 将顶点/边映射到与特定顶点/边关联的附加数据。例如。示例中的 weightmap 将权重(移动成本)与每条边相关联。

  3. predecessor_map 用于记录所有顶点的路径(对于每个顶点，记录从根开始的路径上的前驱)。至于为什么需要它:好吧，这些信息是人们经常希望从算法中得到的东西。

  4. description中清楚地列出了参数.注意这两个版本，一个有命名参数，一个没有(后者在 VC++ 中使用)。

现在逐步了解 the documentation 中给出的示例代码(请注意，我从未真正使用过 Boost.Graph，所以这不能保证正确性，而且我只包含了相关部分并省略了 VC++ 的 #if):

  const int num_nodes = 5;
  //names of graph nodes
  enum nodes { A, B, C, D, E };
  char name[] = "ABCDE";
  //edges of the graph
  Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),
    Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B)
  };
  //weights/travelling costs for the edges
  int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
  int num_arcs = sizeof(edge_array) / sizeof(Edge);

  //graph created from the list of edges
  graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);
  //create the property_map from edges to weights
  property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);

  //create vectors to store the predecessors (p) and the distances from the root (d)
  std::vector<vertex_descriptor> p(num_vertices(g));
  std::vector<int> d(num_vertices(g));
  //create a descriptor for the source node
  vertex_descriptor s = vertex(A, g);

  //evaluate dijkstra on graph g with source s, predecessor_map p and distance_map d
  //note that predecessor_map(..).distance_map(..) is a bgl_named_params<P, T, R>, so a named parameter
  dijkstra_shortest_paths(g, s, predecessor_map(&p[0]).distance_map(&d[0]));

正如我个人在评论中提到的，我发现 lemon使用起来比 Boost.Graph 更直观，所以也许您可能想看看它

关于c++ - Boost的Dijkstra算法教程，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11726857/

ampDijkstragraphlibssectionc++visual-c++boost

有关c++ - Boost的Dijkstra算法教程的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  3. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  4. postman接口测试工具-基础使用教程 - 2

    1.postman介绍Postman一款非常流行的API调试工具。其实，开发人员用的更多。因为测试人员做接口测试会有更多选择，例如Jmeter、soapUI等。不过，对于开发过程中去调试接口，Postman确实足够的简单方便，而且功能强大。2.下载安装官网地址:https://www.postman.com/下载完成后双击安装吧，安装过程极其简单，无需任何操作3.使用教程这里以百度为例,工具使用简单，填写URL地址即可发送请求，在下方查看响应结果和响应状态码常用方法都有支持请求方法:getpostputdeleteGet、Post、Put与Delete的作用get：请求方法一般是用于数据查询，

  5. 在VMware16虚拟机安装Ubuntu详细教程 - 2

    在VMware16.2.4安装Ubuntu一、安装VMware1.打开VMwareWorkstationPro官网，点击即可进入。2.进入后向下滑动找到Workstation16ProforWindows，点击立即下载。3.下载完成，文件大小615MB，如下图：4.鼠标右击，以管理员身份运行。5.点击下一步6.勾选条款，点击下一步7.先勾选，再点击下一步8.去掉勾选，点击下一步9.点击下一步10.点击安装11.点击许可证12.在百度上搜索VM16许可证，复制填入，然后点击输入即可，亲测有效。13.点击完成14.重启系统，点击是15.双击VMwareWorkstationPro图标，进入虚拟机主

  6. hadoop安装之保姆级教程（二）之YARN的配置 - 2

    1.1.1 YARN的介绍 为克服Hadoop1.0中HDFS和MapReduce存在的各种问题⽽提出的，针对Hadoop1.0中的MapReduce在扩展性和多框架⽀持⽅⾯的不⾜，提出了全新的资源管理框架YARN. ApacheYARN（YetanotherResourceNegotiator的缩写）是Hadoop集群的资源管理系统，负责为计算程序提供服务器计算资源，相当于⼀个分布式的操作系统平台，⽽MapReduce等计算程序则相当于运⾏于操作系统之上的应⽤程序。 YARN被引⼊Hadoop2,最初是为了改善MapReduce的实现，但是因为具有⾜够的通⽤性，同样可以⽀持其他的分布式计算模

  7. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  8. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  9. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

  10. ruby - Sinatra + Heroku + Datamapper 使用 dm-sqlite-adapter 部署问题 - 2

    出于某种原因，heroku尝试要求dm-sqlite-adapter，即使它应该在这里使用Postgres。请注意，这发生在我打开任何URL时-而不是在gitpush本身期间。我构建了一个默认的Facebook应用程序。gem文件:source:gemcuttergem"foreman"gem"sinatra"gem"mogli"gem"json"gem"httparty"gem"thin"gem"data_mapper"gem"heroku"group:productiondogem"pg"gem"dm-postgres-adapter"endgroup:development,:t

随机推荐