在附加条件下寻找最快路径

Question

我想知道,如果Dijkstra算法在无向图中有多个直接连接时能够正常工作.

例如:

我想用Dijkstra找到最快的路径,但还有另外一个条件.边上的所有additional_data的总和不能是> = x.因此,如果它出现了重量:3的边缘使用错误,我的程序将尝试第二个边缘.

编辑:我的任务是找到最快的路径,在additional_data边缘的总和不能高于x 的附加条件下.你能告诉我如何处理这个问题吗？

edit2 :(设置赏金)

我一直在研究互联网,直到我发现这个链接.有关如何做我要求的事情的解释.(中上层 acapite)

我试图以某种方式使用它2天,但我担心我不能正确理解这个算法.我想请你们中的一些人帮助我解决这个问题,向我解释一些例子(几个第一步).这是一个例子:

Answer 1

我想你可以修改Dijkstra的算法来处理这个问题.Dijkstra的算法基本上通过逐步构建一个列出每个节点的最短路径的表来工作.您将构建一个表,列出以给定成本到达每个节点的最短路径.或者更确切地说,以给定的成本或更低的成本,即在给定的预算下.

更正式地说,您可以将原始图形转换为另一个图形,然后将Dijkstra应用于该图形.假设additional_data cost总是一个整数,那么转换是:

1. 获取每个原始节点n并为c的每个整数值创建一组节点(n,c),从0到预算值(您可以容忍的additional_data的最大总和)
2. 将每个原始连接n1 - > n2与权重w和additional_data a一起,并创建一组从每个节点(n1,c)到节点(n2,c + a)的连接,每个连接具有权重w

原始图模型中的节点位于空间中.变换后的图模型中的节点位于状态空间中,状态变量是位置,以及到目前为止所花费的预算金额.

如果你想从预算为x的A到Z,那么你只需使用Dijkstra的算法来找到从(A,0)到其中一个节点(Z,c <= x)的路线.

编辑:我已经实现了修改后的Dijkstra算法:https://bitbucket.org/twic/roadsproblem.它的症结在于src/solver.py.

Answer 2

以下是您找到的算法如何处理示例问题的说明.

问题是要找到之间的最短路径node one,并node four用额外的条件,即沿途的累积成本应不超过7.

我们想要找到的解决方案是首先从node one节点转移到节点node two,距离190是成本的4.然后从去node two到node four使用距离的路径195和成本3.总的来说,路径的距离385是成本和成本7.

步骤1

那么算法怎么找到这个呢？第一步是minArray(i,j)像你一样设置矩阵.(i,j)数组的元素保持您必须行进的距离才能到达节点,j并且i剩余的金额完全正确.

启动了有没有访问过的元素和,因为我们在开始node one与7"金钱"左上角元素设置为零.上表中的空白对应infinity于在数组中设置的值.

第2步

接下来,我们找到数组的最低值,这是位置的零(remaining money, node) = (7,1).此元素设置为visited(元素的状态跟踪使用visitedArray相同大小的矩阵minArray),这意味着我们已选择node one.现在,node one通过遍历相应的边来更新连接到的所有节点的值.

这minArray(6,3) = 191意味着我们已经走了很远的距离,191而node three我们留下的钱是6因为我们已经支付了1到达那里的费用.以同样的方式minArray(3,2)设置为190.红色方块标记该元素(7,1)被访问.

第3步

现在我们再次找到最低的未访问元素(即minArray(3,2) = 190),将其设置为visited并更新连接到它的所有元素.这意味着累积距离并通过从当前值中减去成本来计算剩余资金.

请注意,实在是太贵了回去node one的node two.

第4步

下一步,选择minArray(6,3) = 191看起来像这样.

第5步

三步后,阵列看起来像这样.这里说等于两个元素382和等于一个383已经被选中.请注意,元素的值仅在其改善(即低于)当前值时才会更新.

第6步

数组继续填满,直到所有元素都被访问或仍具有无限值.

最后一步

最后一步是通过找到第四列的最低值来找到总距离.我们可以看到最小值minArray(0,4) = 385对应于正确的解决方案.

注意:如果第四列的所有值都是无限的,则意味着没有有效的解决方案.该算法还指定如果在第四列中存在多个相等和最小距离的值,则选择最便宜的一个.