algorithm - 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 长。

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|是标准最短路径的两倍。