c++ - 如何将有向图(邻接表)传递给 Dijkstra 算法 boost 以找到最短路径？

Question

我已经编写了这个类作为构建我的算法的开始，但我可以在控制台上看到 Before 字样，但看不到 After !我在使用 Boost 的 Dijkstra 算法时犯了什么错误？？

#include <myalgorithm.h>
#include<mygraphbuilder.h>
//===============================================
using namespace std;
using namespace boost;
//===============================================

MyAlgorithm::MyAlgorithm()// Default constructor
{
}
//===========================================================================
MyAlgorithm::MyAlgorithm(graph_t AnyGraph, Vertex VSource){//}, Vertex VTarget){ // Parameters Constructor

  MyGraph = AnyGraph;
  vector<Vertex> p(num_vertices(AnyGraph));
  vector<double> d(num_edges(AnyGraph));
  //===========================================================================
  //Dijkstra_Algorithm
  //===========================================================================
  cout<<"Before\t"<<endl;
  dijkstra_shortest_paths(AnyGraph, VSource,
                          predecessor_map(boost::make_iterator_property_map(p.begin(), get(boost::vertex_index, AnyGraph))).
                          distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, AnyGraph))));
 cout<<"After\t"<<endl;
  //===========================================================================
}// End of Parameters Constructor
//===========================================================================
MyAlgorithm::~MyAlgorithm(){ //Destructur
}
//===========================================================================
// Accessors
// function to call ShortPath
vector <Vertex> MyAlgorithm::getShortPath(){
  return MyAlgorithm::ShortPath;
}
// function to call the Graph
graph_t MyAlgorithm::getGraph(){
  return MyGraph;
}
//===========================================================================
// Mutators
//function to set short path Vector as whole
void MyAlgorithm::setShortPath(vector<Vertex> PathVector){
  MyAlgorithm::ResetShortPath();
  MyAlgorithm::ShortPath = PathVector;
}
//function to inject node to Short Path
void MyAlgorithm::setShortPath(Vertex MyNode){
  ShortPath.emplace_back(MyNode);
}
// function to set a graph
void MyAlgorithm::setGraph(graph_t YourGraph){
  MyGraph = YourGraph;
}
//============================================================================
//function to reset short path
void MyAlgorithm::ResetShortPath(){
  MyAlgorithm::ShortPath.clear();
}
//function to Print Out Results
void MyAlgorithm::PrintOut(){
  cout << "distances and parents:" << endl;
  graph_traits < graph_t >::vertex_iterator vi, vend;
  for (boost::tie(vi, vend) = vertices(MyAlgorithm::MyGraph); vi != vend; ++vi) {
      vector<Vertex> p(num_vertices(MyAlgorithm::MyGraph));
      vector<double> d(num_vertices(MyAlgorithm::MyGraph));
      cout << "distance(" << *vi << ") = " << d[*vi] << ", ";
      cout << "parent(" << *vi << ") = " << p[*vi] << endl;
    } // End of Print Loop
}// end of Print Function

我的图表定义如下:

typedef adjacency_list < vecS, vecS, directedS, property < vertex_name_t, idType >, property < edge_weight_t, double > > graph_t;

其中idType为unsigned long long int；但它不起作用，我怎样才能让它起作用？？

Answer 1

我不明白问题是什么。您的代码将简单地编译，参见 Live On Coliru .

说的是

• 你可能不需要多次复制图表就可以做到

• 你应该将距离映射到顶点数而不是边数:

  std::vector<double> d(num_edges(MyGraph));
  

  应该是

  std::vector<double> d(num_vertices(MyGraph));
  

更新

问题中添加的代码:

• 就像我说的，你可能不应该复制那么多。特别是，为什么 MyAlgorithm 拥有 AnyGraph 的拷贝作为成员 MyGraph？它永远不会被您自己的构造函数使用...

• 同样，添加的代码也有同样的问题，具体与

  for (auto v : make_iterator_range(vertices(MyGraph))) {
      std::vector<Vertex> p(num_vertices(MyGraph));
      std::vector<double> d(num_vertices(MyGraph));
      std::cout << "distance(" << v << ") = " << d[v] << ", ";
      std::cout << "parent(" << v << ") = " << p[v] << std::endl;
  }
  

  d 和 p vector 是在循环的每次迭代中使用默认初始化值简单创建的。您希望找到什么？

• 我可以猜测您打算在那里使用dijkstra_shortest_paths 的结果，但您从未采取任何措施来实现这一目标。至少看起来你应该制作 d 和 p 成员变量

• 从未使用过setShortPath 成员函数。通过扩展，ShortPath 成员永远不会被正确设置。您似乎已经意识到这一点，因为您也没有尝试在 PrintOut

中使用它

• 打印“最短路径”存在概念性问题，因为它显然取决于目标顶点...我会编写一个计算特定路径的 getShortPath 访问器:

  Path getShortPath(Vertex destination) {
      Path path;
  
      while (destination != MyGraph.null_vertex()) {
          path.push_front(destination);
          if (destination == src)
              return path;
  
          if (predecessors.at(destination) == destination)
              break;
          destination = predecessors.at(destination);
      }
      throw std::runtime_error("Unreachable");
  }
  

• 现在您可以为任何路径添加打印功能:

  void PrintPath(MyAlgorithm::Path const& path, graph_t const& g) {
      std::cout << "Path: ";
      auto idmap = get(boost::vertex_name, g);
      auto wmap = get(boost::edge_weight, g);
  
      auto previous = g.null_vertex();
      for (auto v : path) {
          if (previous != g.null_vertex()) {
              for (auto e : make_iterator_range(out_edges(previous, g))) {
                  if (target(e, g) == v) {
                      std::cout << " -> (w:" << " << " << wmap[e] << ") ";
                  }
              }
          }
          std::cout << "#" << v << " (id:" << idmap[v] << ") ";
          previous = v;
      }
      std::cout << "\n";
  }
  

  它还在每条边上打印权重(你会看到它与总距离相匹配)

固定演示

这是修复上述所有问题的版本。我停止生成随机图，因为现在“测试用例”假设哪些路径可达:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dag_shortest_paths.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>

using boost::make_iterator_range;

using idType = unsigned long long;

typedef boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::directedS,
    boost::property<boost::vertex_name_t, idType>,
    boost::property<boost::edge_weight_t, double>> graph_t;

struct MyGraphBuilder {
    void generate();
    void printGraph() const;

    graph_t const& getGraph() const { return MyGraph; }
    graph_t&       getGraph()       { return MyGraph; }
  private:
    graph_t MyGraph;
};

void MyGraphBuilder::printGraph() const {
    std::cout << "Number of Vertices is:" << num_vertices(MyGraph) << "\n";
    std::cout << "Number of Edges is:" << num_edges(MyGraph) << "\n";

    boost::print_graph(MyGraph, boost::get(boost::vertex_name, MyGraph), std::cout);

    // to print with edge weights:
    for (auto v : make_iterator_range(vertices(MyGraph))) {
        for (auto oe : make_iterator_range(out_edges(v, MyGraph))) {
            std::cout << "Edge " << oe << " weight " << get(boost::edge_weight, MyGraph, oe) << "\n";
        }
    }
}

void MyGraphBuilder::generate() {
    MyGraph = graph_t(5); // clear graph, 5 vertices

    auto idmap = get(boost::vertex_name, MyGraph);
    idmap[0] = 0ull;
    idmap[1] = 100ull;
    idmap[2] = 200ull;
    idmap[3] = 300ull;
    idmap[4] = 400ull;

    add_edge(1, 3, { 1.52275 }, MyGraph);
    add_edge(2, 0, { 8.79559 }, MyGraph);
    add_edge(2, 0, { 6.41004 }, MyGraph);
    add_edge(3, 2, { 7.37265 }, MyGraph);
    add_edge(4, 0, { 1.18526 }, MyGraph);
}

struct MyAlgorithm {
    using Vertex = graph_t::vertex_descriptor;

    graph_t MyGraph;
    Vertex src;
    std::vector<Vertex> predecessors;
    std::vector<double> distances;

    MyAlgorithm(graph_t const& AnyGraph, Vertex VSource)
        : MyGraph(AnyGraph),
          src(VSource),
          predecessors(num_vertices(MyGraph)),
          distances(num_vertices(MyGraph))
    {
        dijkstra_shortest_paths(MyGraph, src,
                predecessor_map(make_iterator_property_map(predecessors.begin(), get(boost::vertex_index, MyGraph)))
                .distance_map(boost::make_iterator_property_map(distances.begin(), get(boost::vertex_index, MyGraph))));
    }

    using Path = std::deque<Vertex>;
    Path getShortPath(Vertex destination) {
        Path path;

        while (destination != MyGraph.null_vertex()) {
            path.push_front(destination);
            if (destination == src)
                return path;

            if (predecessors.at(destination) == destination)
                break;
            destination = predecessors.at(destination);
        }
        throw std::runtime_error("Unreachable");
    }

    void PrintRawData() const {
        std::cout << "distances and parents:" << std::endl;
        for (auto v : make_iterator_range(vertices(MyGraph))) {
            std::cout << "distance(" << v << ") = " << distances.at(v) << ", ";
            std::cout << "parent(" << v << ") = " << predecessors.at(v) << std::endl;
        }
    }

    graph_t const& getGraph() const { return MyGraph; }
    graph_t&       getGraph()       { return MyGraph; }
};

void PrintPath(MyAlgorithm::Path const& path, graph_t const& g) {
    std::cout << "Path: ";
    auto idmap = get(boost::vertex_name, g);
    auto wmap = get(boost::edge_weight, g);

    auto previous = g.null_vertex();
    for (auto v : path) {
        if (previous != g.null_vertex()) {
            for (auto e : make_iterator_range(out_edges(previous, g))) {
                if (target(e, g) == v) {
                    std::cout << " -> (w:" << " << " << wmap[e] << ") ";
                }
            }
        }
        std::cout << "#" << v << " (id:" << idmap[v] << ") ";
        previous = v;
    }
    std::cout << "\n";
}

int main() {
    MyGraphBuilder builder;
    builder.generate();
    //builder.printGraph();

    MyAlgorithm algo(builder.getGraph(), 1); // 1 is first vertex, not idmap

    algo.PrintRawData();

    auto p0 = algo.getShortPath(0);
    auto p1 = algo.getShortPath(1);
    auto p2 = algo.getShortPath(2);
    auto p3 = algo.getShortPath(3);

    for (auto path : {p0, p1, p2, p3}) {
        PrintPath(path, algo.getGraph());
    }

    // vertex 4 is unreachable:
    try {
        auto p4 = algo.getShortPath(4);
    } catch(std::exception const& e) {
        std::cout << "Error getting path for vertex 4: " << e.what() << "\n";
    }
}

打印

distances and parents:
distance(0) = 15.3054, parent(0) = 2
distance(1) = 0, parent(1) = 1
distance(2) = 8.8954, parent(2) = 3
distance(3) = 1.52275, parent(3) = 1
distance(4) = 1.79769e+308, parent(4) = 4
Path: #1 (id:100)  -> (w: << 1.52275) #3 (id:300)  -> (w: << 7.37265) #2 (id:200)  -> (w: << 8.79559)  -> (w: << 6.41004) #0 (id:0) 
Path: #1 (id:100) 
Path: #1 (id:100)  -> (w: << 1.52275) #3 (id:300)  -> (w: << 7.37265) #2 (id:200) 
Path: #1 (id:100)  -> (w: << 1.52275) #3 (id:300) 
Error getting path for vertex 4: Unreachable