找到最多使用 k 条特殊弧的最短路径
find the shortest path that uses at most k arcs special
我有一个非负权重的图，在这个图中有任何 "special" 弧。
求一个算法，最多使用k"special"条弧，可以找到两个顶点s e t之间的最小路径。
输入：图形，s，t，k。
我考虑过使用一棵以s为根到达t的树，如果有一条路径有超过k条弧的特殊碎片。
此时我应该有一个 DAG 并使用任何算法来找到最小距离。
我有两种方法：
第一种方法：
对于每个顶点 u，计算从源 s 到该顶点的 k+1 最短路径。所以每个顶点都有一个数组 dst = {d0, d2, d3, .... , dk}，其中 di 是从 s 到 u 的最短路径，正好使用 i 特殊弧。
现在您可以使用 dikstra's algorithm 的一种变体来解决这个问题，您有 k + 1 个优先级队列，而不是一个优先级队列，每个优先级队列对应一个值 i : 0 <= i <= k。
第二种方法（更优雅）：
假设您有一栋有 k + 1 层的建筑物。每层楼都有一份图表；然而，特殊的弧线充当相邻楼层之间的楼梯。因此，如果原始图中的顶点 u 顶点 v 之间有一条特殊弧线，则 floor j (0 <= j <= k-1) 中的每个顶点 u 和每个顶点 v 在楼层 j + 1。所以在这个新图中，从 floor0 中的顶点 u 到 floorj 中的顶点v 的任何路径都恰好使用 j 特殊弧。然后在新图中，你不能使用超过k的特殊弧线从任何顶点u到任何其他顶点v，因为你最多只能爬上k层。您可以使用 Dikstra 的算法来解决从 floor0.
中的源顶点开始的新图上的问题
运行时间是O(k * |E| + k * |V| * log(k*|V|))。
我有一个非负权重的图，在这个图中有任何 "special" 弧。 求一个算法，最多使用k"special"条弧，可以找到两个顶点s e t之间的最小路径。 输入：图形，s，t，k。
我考虑过使用一棵以s为根到达t的树，如果有一条路径有超过k条弧的特殊碎片。 此时我应该有一个 DAG 并使用任何算法来找到最小距离。
我有两种方法：
第一种方法：
对于每个顶点 u，计算从源 s 到该顶点的 k+1 最短路径。所以每个顶点都有一个数组 dst = {d0, d2, d3, .... , dk}，其中 di 是从 s 到 u 的最短路径，正好使用 i 特殊弧。
现在您可以使用 dikstra's algorithm 的一种变体来解决这个问题，您有 k + 1 个优先级队列，而不是一个优先级队列，每个优先级队列对应一个值 i : 0 <= i <= k。
第二种方法（更优雅）：
假设您有一栋有 k + 1 层的建筑物。每层楼都有一份图表；然而，特殊的弧线充当相邻楼层之间的楼梯。因此，如果原始图中的顶点 u 顶点 v 之间有一条特殊弧线，则 floor j (0 <= j <= k-1) 中的每个顶点 u 和每个顶点 v 在楼层 j + 1。所以在这个新图中，从 floor0 中的顶点 u 到 floorj 中的顶点v 的任何路径都恰好使用 j 特殊弧。然后在新图中，你不能使用超过k的特殊弧线从任何顶点u到任何其他顶点v，因为你最多只能爬上k层。您可以使用 Dikstra 的算法来解决从 floor0.
运行时间是O(k * |E| + k * |V| * log(k*|V|))。