3

我有一个带有正边权重和正节点权重的图表。路径的长度定义为沿路径的所有边权重之和，加上沿路径遇到的最大节点权重。

我最初认为修改后的 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 长。

4

2 回答 2

0

如果你可以原谅一阶更大的多项式时间，那么相当简单的算法：

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| 比你的标准最短路径多倍。

于 2013-09-21T20:08:57.167 回答
0

你的图表一开始就不是很清楚（蓝色的值太多，角色不明确），这使得答案变得更加困难。这篇文章中有一个更好的问题、一个更简单的图表和一些直接的答案。

对我来说清楚并允许我纠正我的实现并获得正确结果的是，在循环中的每次重复结束时，是时候选择下一个节点/顶点，我应该检查其未访问的邻居，我必须从整个未访问的顶点池中进行选择，而不仅仅是从当前检查的节点的未访问邻居中进行选择。我的错误印象是，一旦您在十字路口选择了一条路径，由于算法的贪婪性会将您带到那里，您只能沿着它走到最后，在未访问的节点之后未访问。不。您每次都根据最小的暂定值选择下一个全局未访问的节点，而不管它在图中的位置或是否连接到当前节点。

我希望这能消除像我这样的其他人所经历的困惑，并将他们带到这里。

于 2019-02-19T14:03:56.730 回答