algorithm - 具有多个条件的 SP

Question

假设我们有一个有向 G(V,E) 图，其边上的权重为正。该图的边也为黑色或绿色。给定起始顶点 u，我们需要找到从 u 开始的最小路径(权重)到 V 的所有顶点。尽管这些路径最多必须有 k 个绿色边(其中 k 是正整数)。有什么想法吗？

Answer 1

您可以从创建 k + 1 开始图 G_i由顶点和黑边的副本组成:

• 对于每个 v in V你创造v_0, v_1, ... v_k
• 对于每条黑边(u, v) in E你创造(u_i, v_i)对于所有 0 <= i <= k

这些中的每一个 G_i代表你使用了i之后的状态绿色边缘已经。所以我们可以通过添加绿色边来连接这些图:

• 每一个绿色(u, v) in E你创造边缘(u_i, v_{i+1})对于所有 0 <= i < k .

边缘是有向的，所以你不能“向后”移动，即，已经使用的绿色边缘的数量永远不会减少。

最后，添加汇点:

• 对于每个 v in V你创造v_s和边缘 (v_i, v_s)所有 0 <= i <= k 的权重为 0 .

这些汇点允许的是确定到顶点的最小距离v对于每个使用的绿色顶点数。

---

现在，只需运行 Dijkstra 的起始顶点 u_0 .对于所有 v in V , v_s 的结果是到u的最短距离至 v最多使用 k绿色边缘。

---

Dijkstra 的运行时间是O(|E| + |V| log |V|) .我们的顶点总数是O(k) * |V|边的总数是O(k) * |E| , 所以最终运行时间为

O(k|E| + k|V| log k|V|)