问双权图Dijkstra算法的变分

EN

假设你想同时优化两个标准:距离和吸引力(假设路径吸引力被定义为最吸引人的边缘的吸引力，尽管你可以想出不同的定义)。下面的Dijkstra的变化可以证明是有效的，但我认为它主要是有用的，当其中一个标准需要少量的值-例如吸引力为1，.，k对于一些小的固定k(较小的i更好)。

Dijsktra算法的标准伪码使用单个优先级队列。相反，使用k优先级队列。优先级队列i将在Dijkstra算法中对应于具有吸引力I的节点v∈V的最短路径。

首先初始化每个节点位于距离为∞的每个队列中(因为，最初，具有吸引力的v的最短路径是无限的)。

在主Dijkstra循环中，它说

 while Q is not empty

将其更改为

 while there is an i for which Q[i] is not empty
     Q = Q[i] for the lowest such i

然后从那里继续。

请注意，当您更新时，您将弹出队列Q[i]，并为j≥i插入到Q[j]中。

可以修改Dijkstra的松弛性质的证明，以证明这是可行的。

请注意，您将获得最多k_个结果，作为每个节点和吸引度，你可以有最短的距离到具有给定吸引度的节点。

示例

以评论中的一个例子：

因此，基本上，如果一条路径有超过10英里的无覆盖里程，那么我们就选择另一条路径。

在这里，假设英里是整数(或者可以四舍五入为整数)，我们可以创建11个队列:队列i对应于与i无覆盖英里的最短距离，除了10英里，后者对应于10或更高的无覆盖里程。

在算法的某个点，假设所有队列在队列3下面都是空的。我们弹出队列3，并更新顶点的邻居:如果从弹出节点到另一个节点的距离为1，这可能会更新队列4中的某个节点。

当算法运行时，它输出(节点，无覆盖距离)→最短距离的映射.在这里，您可以决定放弃对中的第二项为10的所有映射。