algorithm - 在有向加权图中找到两个节点之间的最短路径

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

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

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

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

Dijkstra 是贪心的，所以你要弄清楚的是:是否有可能一旦确定了最短路径，就可以找到另一条更短的路径。因为您会发现路径的长度越来越长，所以这是不可能的。