最短路径图算法助力Boost

我有一个矩形网格形状的 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 Graph Library。

对于那些感兴趣的人，我正在尝试实施福克斯的建议 paper.

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

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

但我提到的论文说有更快的算法（但对我来说烦人的是没有提供实现），而且那就是

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

所以，这是你的问题，

1. DAG 无循环
2. 权重 > 0
3. 左侧重量

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

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

请记住，DAG 可以画成一条线。为了DAG 线性化 here http://jason-kok.appspot.com/algorithm/dynamic是一个有趣的资源。

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

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

当然递归的起点是

MinimumPath(Source,Source)

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

一个好的实现是here http://www.geeksforgeeks.org/shortest-path-for-directed-acyclic-graphs/.

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