有向加权图中两个节点间最短路径的求取

Question

我有一个有向加权图G = <V, E>。我需要在s和t之间找到最短的O((V + E)*logV)路径。这将是一个非常简单的任务，如果我有一个经典的度量权重的路径。但事实并非如此。

Weight of path = two heaviest edges in this path。

因此，经典的Dijkstra's algorithm with modified binary heap不起作用。我认为，我必须修改这个算法。我正试着去做，但我没有成功。

Example.

​

​

3与5之间的路径权重=4+2=6

3与7之间的路径权重=4+4=8

Answer 1

根据的反例编辑了我的答案。

你在问题中给出的例子并不是Dijkstra何时不起作用的好例子。

我相信你可以通过修改Dijkstra来做到这一点。关键是要跟踪每个顶点的多个备选方案。您不仅必须存储构成最短路径的weigth，还必须存储max < shortest.max和min > shortest.min中的备选方案。

Dijkstra是贪婪的，所以你必须弄清楚:一旦确定了最短路径，是否有可能找到另一条更短的路径。因为您将在增加的长度中发现路径，所以这是不可能的。