c++ - 最短路径图算法帮助Boost

Question

我有一个矩形网格形状的 DAG，其中水平边缘始终指向右侧，垂直边缘始终指向下方。边缘具有与之相关的正成本。由于矩形格式，使用从零开始的行/列引用节点。这是一个示例图:

现在，我想进行一次搜索。起始顶点将始终位于左列(索引为 0 的列)和图形的上半部分。这意味着我将选择起点为 (0,0)、(1,0)、(2,0)、(3,0) 或 (4,0)。目标顶点总是在右列(索引为 6 的列)并且“对应”于起始顶点:

起始顶点(0,0)对应目标顶点(5,6)

起始顶点(1,0)对应目标顶点(6,6)

起始顶点(2,0)对应目标顶点(7,6)

起始顶点(3,0)对应目标顶点(8,6)

起始顶点(4,0)对应目标顶点(9,6)

我只是提到这个来证明目标顶点总是可以到达的。这对我的实际问题可能不是很重要。

我想知道的是我应该使用什么搜索算法来找到从开始到目标的路径？我正在使用 C++ 并可以访问 Boost 图形库。

对于那些感兴趣的人，我正在尝试实现 Fuchs 从他的 Optimal Surface Reconstruction from Planar Contours 中提出的建议纸。

我看过 A*，但老实说我不明白它，也不知道启发式是如何工作的，甚至不知道我是否能想出一个!

由于矩形形状和规则的边缘方向，我认为可能有一个非常适合的算法。我考虑过迪杰斯特拉

但我提到的论文说有更快的算法(但令我恼火的是没有提供实现)，另外就是

单一来源，我想我想要一对。

Answer 1

所以，这是你的问题，

1. DAG 无循环
2. 权重 > 0
3. 左体重 < 右体重

您可以使用简单的详尽搜索来定义每条可能的路线。所以你有一个 O(NxN) 算法。然后你会选择最短的路径。这不是一个非常聪明的解决方案，但它是有效的。

但我想你想比这更聪明，让我们考虑一下，如果一个特定的节点可以从两个节点到达，你可以找到两个节点的权重加上到达当前节点的成本的最小值。您可以将此视为先前详尽搜索的扩展。

请记住，DAG 可以画成一条线。对于DAG 线性化 here是一个有趣的资源。

现在您刚刚定义了一个递归算法。

MinimumPath(A,B) = MinimumPath(MinimumPath(A,C)+MinimumPath(A,D)+,MinimumPath(...)+MinimumPath(...))

递归的起点当然是

MinimumPath(Source,Source)

当然是0。 据我所知，boost 没有开箱即用的算法来做到这一点。但这实现起来非常简单。

一个好的实现是here .

如果出于某种原因，您没有 DAG，则应使用 Dijkstra 或 Bellman-Ford。