C++ BGL Dijkstra 具有数字顶点 ID 和多个目标的最短路径

问题描述 投票：0回答：1

我一直在浏览本网站上的帖子、图书馆的文档以及其他网站上的讨论和解释。但是，我很难理解 C++ Boost Graph 库在我的应用程序中如何工作。我的问题以粗体突出显示。我按照时间顺序列出了它们所指的功能部分。不过，最底层的问题是最重要的。

考虑以下使用 C++ 17 的示例：

#include <vector>
#include <boost/config.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/property_map.hpp>

typedef boost::adjacency_list <boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::property<boost::edge_weight_t, double> > graph_t;
typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_descriptor;

void example_paths(std::vector<int>& from, std::vector<int>& to, std::vector<double>& weights, int source, std::vector<int>& targets) {

}

输入向量 

from
、
to
和 
weights
每个都有大约 22 亿个元素，表示图的边。 
from
托管源 ID、
to
目的地 ID 和 
weights
边权重。 IE。第一条边从顶点 
from[0]
到顶点 
to[0]
，并且权重为 
weights[0]
。该数据创建了一个包含约 2.5 亿个顶点的图。几乎所有顶点都连接到主图。严格来说，它是一个多图，但是在这个库中称为由多个图组成的图。从该图中，我想计算从 ID 为 
source
的顶点到 ID 为 
targets
的顶点的最短路径。

在我的代码中，我遵循 文档的示例，并将 

OutEdgeList
定义为 
boost::listS
，将 
VertexList
定义为 
boost::vecS
。我读到，可用于 
boost::vecS
和 
boost::listS
的类型（
boost::slistS
、
boost::setS
、
boost::multisetS
、
boost::hash_setS
、
OutEdgeList
和 
VertexList
）在计算效率方面有所不同。由于我必须考虑总的计算效率，同时考虑到输入向量的图构造和 Dijkstra 算法的应用，我不知道应该选择哪种类型。 我应该为 
OutEdgeList
和 
VertexList
使用什么类型？

这引出了我的第二个问题。我发现了两种截然不同的邻接表构建方法：

graph_t g;
for(int i = 0; i < from.size(); i++) {
  boost::add_edge (from[i], to[i], weights[i], g);
}

和

typedef std::pair< int, int > Edge;
const int num_nodes = 5;
enum nodes { A, B, C, D, E };
char name[] = "ABCDE";
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) };
int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
int num_arcs = sizeof(edge_array) / sizeof(Edge);
graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);

第二种方法取自文档，并未根据我的应用程序进行调整。 哪种方法更有效？如果是第二种，我的示例的翻译是什么？我使用数字而不是字符 ID 有问题吗？

总的来说，我想实现这个最短路径函数的三个变体。第一个变体仅获取沿最短路径的顶点 ID。 IE。它生成一个 

std::vector<std::vector<int> >
，其中第一个元素是从 
source
到 
targets[0]
等的向量。第二个变体仅返回距离，即 
std::vector<double>
，其中第一个元素是沿最短路径的边权重之和之间 
source
和 
targets[0]
等。第三个变体返回其他两个变体的输出。据我了解，计算最短路径的工作原理如下

std::vector<vertex_descriptor> p(num_vertices(g));
std::vector<double> d(num_vertices(g));
vertex_descriptor s = vertex(1, g);
std::set<vertex_descriptor> t = {vertex(5, g), vertex(7, g)};

boost::dijkstra_shortest_paths(g, s, boost::predecessor_map(&p[0]).distance_map(&d[0]).visitor(target_visit(targets, on_examine_vertex())));

我可以在其中添加或省略部分，具体取决于我是否要提取沿路径的距离或顶点 ID。不过，我不太明白它是如何工作的。 如何调用 

boost::dijkstra_shortest_paths
来获取上述三个函数变体中的 
std::vector
？

我对这篇冗长的文章感到抱歉。我想这些问题对于有这个库经验的人来说是很直观的，但我已经被困在这些问题上好几天了。我知道这个平台上的一些人对以下问题很敏感：询问效率，但处理数十亿条边需要将计算效率作为首要考虑因素。

如果我的帖子的部分内容需要澄清，请随时提问。

提前致谢。

c++ graph-theory shortest-path dijkstra boost-graph
1个回答
0
投票

如何调用 boost::dijkstra_shortest_paths 来获取 上述三个函数变体中的每一个中都有 std::vector 吗？

一次调用 boost::dijkstra_shortest_paths() 即可为您提供所需的所有数据。要以您想要的形式提取数据，需要解决阻碍 boost::graph

的“语法糖”

变体 1：从源到所有目标的路径

这需要通过父向量从目标回溯到源。像这样：

std::vector<std::vector<int>> Variant1(
    graph_t &g,
    const std::vector<int> &p)
{
    std::vector<std::vector<int>> ret;
    for (int target = 1; target < name.length(); target++)
    {
        std::vector<int> path;
        int vertex = target;
        while (vertex != 0)
        {
            path.push_back(vertex);
            vertex = p[vertex];
        }
        std::reverse(path.begin(), path.end());
        ret.push_back(path);
    }
    return ret;
}

变体 2：从源到所有目标的距离

距离向量直接给你这个

变体 3：返回其他两个变体的输出。

正如它所说。

您可以一次完成所有三件事，如下所示：

dijkstra_shortest_paths(
    g, s,
    predecessor_map(boost::make_iterator_property_map(
                        p.begin(), get(boost::vertex_index, g)))
        .distance_map(boost::make_iterator_property_map(
            d.begin(), get(boost::vertex_index, g))));

displayVariant1(Variant1(g, p));
displayVariant2(g, d);
displayVariant3(g, p, d);

输出：

Variant1:
Path from A to C: C D E B
Path from A to C: C
Path from A to C: C D
Path from A to C: C D E

Variant2:
distance from A to A = 0
distance from A to B = 6
distance from A to C = 1
distance from A to D = 4
distance from A to E = 5

Variant3:
Path from A to A:  C D E B Total distance: 0
Path from A to B:  C Total distance: 6
Path from A to C:  C D Total distance: 1
Path from A to D:  C D E Total distance: 4
Path from A to E:  Total distance: 5

整个应用程序的完整代码位于 https://gist.github.com/JamesBremner/30a8120ffac6ce884a5ee290eff9d08e

有关处理巴洛克式 boost::graph 文档的一般评论，请参阅 https://stackoverflow.com/a/1514439/16582

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.