找到最多使用最多k個弧線的最短路徑

Question

我有一個非負的權重圖，在此圖中有任何「特殊」弧。 找到一個算法，可以找到兩個頂點之間的最小路徑，最多使用k個「特殊」弧。 輸入：圖形，s，t，k。

我想過如果有一個超過k個弧的特殊廢品的路徑，使用植根於s到達t的樹。 在這一點上，我應該有一個DAG，並使用任何算法來找到最小距離。

Answer 1

我有兩種方法：

第一方法： 對於每個頂點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之間有特殊弧線，則在j (0 <= j <= k-1)樓層的每個頂點u與j + 1樓層的每個頂點v之間都會有一條弧線。因此，在這張新圖中，從地板0中的頂點u到地板j中的頂點v的任何路徑恰好使用j特殊弧。然後在新圖中，不能從任何頂點u到任何其他頂點v，因爲只能爬到最多k層，所以使用多於k特殊弧。您可以使用Dikstra的算法來解決在0樓層以源頂點開始的新圖上的問題。

運行時間爲O(k * |E| + k * |V| * log(k*|V|))。