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 |超过标准最短路径的时间。

Answer 2

你的图表开头并不是那么清楚（蓝色的角色太多不明确），这使得答案更加困难。一个更好的问题，一个更简单的图表和一些直接的答案in this post。

什么让我清楚，并允许我纠正我的实现并获得正确的结果，是在循环中的每次重复结束时，是时候选择下一个节点/顶点，我应该检查其未访问的邻居，我不得不从整个未访问的顶点池中挑选，而不仅仅是从当前检查的节点的未访问的邻居中挑选。我错误地认为，一旦你在十字路口选择一条路径，因为算法的贪婪性质会带你到那里，你只能跟着它走到最后，在未访问的节点之后没有访问过。不会。您每次都会根据最小的暂定值选择下一个全局未访问的节点，无论其在图表中的位置或是否连接到当前节点。

我希望能够清除像我这样的人所经历的混乱，并将他们带到这里。