Dijkstra最短路径算法无法解决问题

Question

我有一张拥有正权边和正权节点的图表。路径的长度被定义为沿着路径经过的所有边权重的总和，再加上沿途遇到的最大节点权重。

我最初认为修改后的Dijkstra算法可以解决这个问题，但我发现了一个测试用例它无法通过。我该如何解决这个问题？是否有任何标准算法可供参考？

我的修改版Dijkstra算法如下：在每个节点处，我记录到目前为止的最短路径，以及到目前为止所见过的最大节点权重，并使用它来计算邻居节点的路径长度。请参阅我的评论获取详细信息。

这是一个Dijkstra算法无法通过的图： http://i.imgur.com/FQhRzXV.jpg 绿色数字是节点标签。蓝色是权重（节点和边权重）。假设我想计算节点1和7之间的最短路径（用绿色标记）。Dijkstra算法的问题在于节点4始终记录路径1-8-9-4，因为它比路径1-2-3-4更短（前者长度为9，后者长度为13）。但是要到达节点7，路径1-8-9-4-5-6-7比路径1-2-3-4-5-6-7更长。

- elexhobby

---

你尝试了什么？为什么失败了？我相信修改后的 Dijkstra 算法会行 :-) - Jean Logeart

修复起始节点。对于每个邻居，存储一对数字 - （到该邻居的最短路径，到该节点路径上遇到的最大节点权重）。将它们放入队列中并选择具有最短路径的节点。继续执行。当添加一个连接到已访问节点a的新节点b时，如果b的权重小于到节点a的路径上遇到的最大节点权重，则b上的一对数字为（到a的最短路径+边缘权重ab，直到a为止遇到的最大节点）。否则，b上的一对数字为（到a的最短路径-到a为止的最大节点+节点b的权重+边缘权重ab，节点b的权重）。 - elexhobby

@DanielV 通过路径的权重，我指的是边权重+到目前为止遇到的最大节点权重。因此，您所称之为总权重包括到目前为止遇到的最大节点权重，而不仅仅是边权重之和。为了澄清，在每个节点上对成对数值的第一个数字是（边权重之和+到目前为止遇到的最大节点权重，到目前为止遇到的最大节点权重）。 - elexhobby

考虑一个包含2个顶点s和t的图G，具有以下属性：(1)从s到t恰好有2条不同的路径；(2)第一条路径的边权重为{2, 1, 1, 1, 1}；(3)第二条路径的边权重为{1, 1, 100}。大多数朴素算法会将s-t路径计算为201而不是8，如果我正确理解您的意思，那么您的算法应该可以得出正确答案。 - DanielV

我认为你应该展示一些代码，或者至少是一些伪代码，以更正式地描述你所做的事情。最好附带一些你的方法失败的例子(也有一些成功的例子会很好)。 - TooTone

Answer 1

如果您可以容忍多一个阶数的多项式时间，那么有一个相当简单的算法：

ModifiedShortestPath(u, v, G) {
  X = StandardardShorestPath(u, v, G);
  E = heaviest edge in X
  F = all edges in G of weight >= E
  Y = ModifiedShortestPath(u, v, G - F); // recur here on G without the F edges
  return Min(X, Y);
}

这个程序的运行时间是标准最短路径的|E|倍。

- DanielV

Answer 2

你的图表一开始就不够清晰（蓝色值太多且不明确），这使得答案变得更加困难。更好的问题应该是，一个更简单的图表和一些直接的答案在这篇帖子中。

让我明确的是，在循环的每次重复结束时，当需要选择下一个节点/顶点时，我需要检查其未访问的邻居，我必须从所有未访问的顶点中选择，而不仅仅是从当前检查节点的未访问邻居中选择。我错误地认为，在岔路口选择路径后，由于算法的贪婪性质将你带到那里，因此你只能按顺序跟随它到达未访问的节点。不。每次都基于最小试探值选择下一个全局未访问的节点，无论其在图表中的位置如何或者它是否与当前节点相连接。

我希望这可以澄清其他像我一样经历过并导致他们来到这里的困惑。

- Κωστής Καρβουνιάρης