查找圖中兩個節點之間固定跳數的最短路徑

Question

如果G = {V，E}是一個無向，連通，未加權的圖，v是源頂點，u是目的頂點，我需要找到最短路徑他們。問題是，我只允許以k尺寸的固定跳數移動。例如，如果k = 3，則來自某個頂點v的可到達頂點就是所有頂點，它們之間存在長度爲3的路徑，這些路徑不會在同一個邊上兩次遍歷。從v到u的每一跳都不得在同一條邊上兩次。但是，一連串的躍點可以在相同的邊緣上移動數次。 到目前爲止，我已經嘗試了幾種方法，但沒有取得任何成功，但我有一種感覺，那就是涉及動態編程。有任何想法嗎？

Answer 1

一個解決方案是創建具有與G相同的頂點集的圖G' = {V,E'}，但邊緣集由原始圖中的一組跳躍點組成，然後在G'上使用Dykstra算法。