最短路径图算法有助于Boost [英] Shortest path graph algorithm help 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库.
对于那些感兴趣的人，我正在尝试从他的解决方案
所以，这是您的问题，
- DAG没有周期
- 权重> 0
- 左体重<合适的体重
您可以使用简单的详尽搜索来定义所有可能的路线.因此，您有一个O(NxN)算法.然后，您将选择最短的路径.这不是一个非常聪明的解决方案，但它是有效的.
但是我想您想变得更聪明，让我们考虑一下，如果可以从两个节点到达一个特定的节点，则可以找到两个节点的最小权重加上到达当前节点的成本.您可以将其视为先前详尽搜索的扩展.
请记住，DAG可以画一条线.对于 DAG线性化 此处是一个有趣的资源. >
现在，您刚刚定义了一个递归算法.
MinimumPath(A,B) = MinimumPath(MinimumPath(A,C)+MinimumPath(A,D)+,MinimumPath(...)+MinimumPath(...))
当然，递归的起点是
MinimumPath(Source,Source)
，当然是0. 据我所知，boost并没有开箱即用的算法可以做到这一点.但这很容易实现.
此处.
>如果由于某种原因您没有DAG，则应使用Dijkstra或Bellman-Ford.
I have a rectangular grid shaped DAG where the horizontal edges always point right and the vertical edges always point down. The edges have positive costs associated with them. Because of the rectangular format, the nodes are being referred to using zero-based row/column. Here's an example graph:
Now, I want to perform a search. The starting vertex will always be in the left column (column with index 0) and in the upper half of the graph. This means I'll pick the start to be either (0,0), (1,0), (2,0), (3,0) or (4,0). The goal vertex is always in the right column (column with index 6) and "corresponds" to the start vertex:
start vertex (0,0) corresponds to goal vertex (5,6)
start vertex (1,0) corresponds to goal vertex (6,6)
start vertex (2,0) corresponds to goal vertex (7,6)
start vertex (3,0) corresponds to goal vertex (8,6)
start vertex (4,0) corresponds to goal vertex (9,6)
I only mention this to demonstrate that the goal vertex will always be reachable. It's possibly not very important to my actual question.
What I want to know is what search algorithm should I use to find the path from start to goal? I am using C++ and have access to the Boost Graph Library.
For those interested, I'm trying to implement Fuchs' suggestions from his Optimal Surface Reconstruction from Planar Contours paper.
I looked at A* but to be honest didn't understand it and wasn't how the heuristic works or even whether I could come up with one!
Because of the rectangular shape and regular edge directions, I figured there might be a well-suited algorithm. I considered Dijkstra
but the paper I mention said there were quicker algorithms (but annoyingly for me doesn't provide an implementation), plus that's
single-source and I think I want single-pair.
So, this is your problem,
- DAG no cycles
- weights > 0
- Left weight < Right weight
You can use a simple exhaustive search defining every possible route. So you have a O(NxN) algoririthm. And then you will choose the shortest path. It is not a very smart solution, but it is effective.
But I suppose you want to be smarter than that, let's consider that if a particular node can be reached from two nodes, you can find the minimum of the weights at the two nodes plus the cost for arriving to the current node. You can consider this as an extension of the previous exhaustive search.
Remember that a DAG can be drawn in a line. For DAG linearization here's an interesting resource.
Now you have just defined a recursive algorithm.
MinimumPath(A,B) = MinimumPath(MinimumPath(A,C)+MinimumPath(A,D)+,MinimumPath(...)+MinimumPath(...))
Of course the starting point of recursion is
MinimumPath(Source,Source)
which is 0 of course. As far as I know, there isn't an out of the box algorithm from boost to do this. But this is quite straightforward to implement it.
A good implementation is here.
If, for some reason, you do not have a DAG, Dijkstra's or Bellman-Ford should be used.
这篇关于最短路径图算法有助于Boost的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
