尋找最廉價的路徑與忽略一個成本

Question

我想找到2個頂點之間的最廉價的路徑，我可以選擇，我可以去免費的路徑，例如：

最便宜的頂點之間的路徑1和6是1-3-4-5-6 - 我免費獲得邊緣1-3（成本30），並且總共花費21美元。

是否有任何其他方式檢查所有路徑一？

Answer 1

一種方式做到這一點是做到以下幾點：

1. 複製你的圖形，讓你有你的原始圖G與節點1,2等。和具有節點1'，2'等的副本G'。和相應的邊緣。
2. 對於G的每條邊（a，b），從a到b'以及另一個從b到a'形成一條弧（直接！），兩者的代價均爲0.
3. 最後，使用任何最短路徑算法子圖G的任何頂點到G'的任何頂點（在你的例子中是1到6）。

基本上發生的事情是，當你使用你的小丑時，你從子圖G切換到G'。

通過添加額外的副本並將每個新副本鏈接到最後一個，您可以從那裏推廣到任意數量的小丑邊。然而，在這種情況下，您可能不得不使用較少的jokers添加目標，以便說明最短路徑比您擁有較少的邊界的情況。