具有多个条件的 SP
SP with multiple criteria
假设我们有一个带正权重的有向 G(V,E) 图 edges.This 图的边也是黑色或 green.Given 一个起始顶点，我们需要找到最小路径（重量）从 u 到 V.These 路径的所有顶点，但必须有最多 k 个绿色边（其中 k 是正整数）。有什么想法吗？
您可以先创建 k + 1 个图 G_i，其中包含顶点和黑边的副本：
- 你每
v in V 创建 v_0, v_1, ... v_k
- 对于每个黑边
(u, v) in E，您为所有 0 <= i <= k 创建 (u_i, v_i)
每个 G_i 代表您已经使用 i 绿色边缘后的状态。所以我们可以通过添加绿色边来连接这些图：
- 对于每个果岭
(u, v) in E，您为所有 0 <= i < k 创建边缘 (u_i, v_{i+1})。
边缘是有向的，所以你不能移动"backwards"，即已经使用的绿色边缘的数量永远不会减少。
最后，添加汇点：
- 对于每个
v in V，您创建 v_s 并为所有 0 <= i <= k.[=61 创建边 (v_i, v_s)，权重为 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|，所以最后的运行ning时间是
O(k|E| + k|V| log k|V|)
假设我们有一个带正权重的有向 G(V,E) 图 edges.This 图的边也是黑色或 green.Given 一个起始顶点，我们需要找到最小路径（重量）从 u 到 V.These 路径的所有顶点，但必须有最多 k 个绿色边（其中 k 是正整数）。有什么想法吗？
您可以先创建 k + 1 个图 G_i，其中包含顶点和黑边的副本：
- 你每
v in V创建v_0, v_1, ... v_k - 对于每个黑边
(u, v) in E，您为所有0 <= i <= k 创建
(u_i, v_i)
每个 G_i 代表您已经使用 i 绿色边缘后的状态。所以我们可以通过添加绿色边来连接这些图：
- 对于每个果岭
(u, v) in E，您为所有0 <= i < k创建边缘(u_i, v_{i+1})。
边缘是有向的，所以你不能移动"backwards"，即已经使用的绿色边缘的数量永远不会减少。
最后，添加汇点：
- 对于每个
v in V，您创建v_s并为所有0 <= i <= k.[=61 创建边(v_i, v_s)，权重为 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|，所以最后的运行ning时间是
O(k|E| + k|V| log k|V|)