algorithm - 找到最多使用 k 条特殊弧的最短路径

Question

我有一个没有负权重的图，在这个图中有任何“特殊”弧。找到一种算法，它可以找到两个顶点 s e t 之间的最小路径，最多使用 k 个“特殊”弧。输入:图形，s，t，k。

我考虑过使用一棵以 s 为根到达 t 的树，如果有一条路径有超过 k 条弧的特殊碎片。此时我应该有一个 DAG 并使用任何算法来找到最小距离。

Answer 1

我有两种方法:

第一种方法:对于每个顶点 u , 计算 k+1来自源的最短路径 s到那个顶点。所以每个顶点都有一个数组 dst = {d0, d2, d3, .... , dk}其中 di是从 s 开始的最短路径至 u完全使用 i特殊弧线。现在您可以使用 dikstra's algorithm 的变体为了解决这个问题，你有 k + 1 而不是一个优先级队列优先级队列，其中每个队列对应一个值 i : 0 <= i <= k .

第二种方法(更优雅):想象你有一栋建筑有 k + 1地板。每层楼都有一份图表；然而，特殊的弧线充当相邻楼层之间的楼梯。所以如果你在顶点 u 之间有一条特殊的弧顶点 v在原始图中，每个顶点之间会有一条弧 u在地板上 j (0 <= j <= k-1)和每个顶点 v在地板上 j + 1 .所以在这个新图中，从顶点 u 开始的任何路径在地板上 0到顶点 v在地板上 j完全使用 j特殊弧线。然后在新图中，你不能从任何顶点开始 u到任何其他顶点 v使用超过 k特殊弧线，因为你最多只能爬 k 层楼。您可以使用 Dikstra 的算法来解决从 floor 0 中的源顶点开始的新图上的问题。 .

运行时间为O(k * |E| + k * |V| * log(k*|V|)) .