圖的遍歷算法的折扣

我有加權邊有向圖，我想找到我的圖表中的所有對最短路徑。但我希望能夠考慮折扣。圖的遍歷算法的折扣

例如：

A->B with weight 10 
A->C with weight 20 
B->C with weight 10 
C->D with weight 10 
A->B->C with weight 15 because I get a discount of 5 if and only if I visit B first. (see clarification) 

A->B->C->D should therefor have weight 25 while 
A->C->D with weight 30

是否有實現這個的方法嗎？我已經看過了各種算法（弗洛伊德 - 沃肖爾等），但他們似乎沒有認識到這個問題...

編輯：澄清：只有組合（A-> B-> C）得到折扣。

E->(A->B->C)->F gets it because it has the exact combination in its path, but 
A->E->B->C  does not get it

來源

2014-10-07 sandbox

你得到的折扣，如果你去'A-> E-> B-> F-> C'？ – 2014-10-07 23:25:45

沒有，如果是A-> B-> C^ – sandbox 2014-10-07 23:34:20

這仍然是一個問題的定義不夠僅適用折扣。所描述的所有折扣集究竟如何？「如果我先訪問B」這個短語有很多不同的含義。 – Gene 2014-10-07 23:41:49

您可以通過添加邊和虛擬節點來表示折扣來擴充您的圖。舉例來說，如果你有一個路徑A->B->C打折，添加一個新的節點B'與僅邊緣：

A->B' 
B'->C

這樣

w(A,B') + w(B',C) = w(A,B) + w(B,C) - discount

其中w(S,T)是邊緣S->T的重量。不要緊，你申請貼現到邊緣，所以你可以有

w(A,B') = 10, w(B',C) = 5, or 
w(A,B') = 5 , w(B',C) = 10

請注意，如果你有一個節點Q，唯一的邊緣入射的原始圖Q是：

S->Q 
Q->T

和折扣將被施加的路徑S->Q->T，添加新節點Q'是多餘的。您可以安全地將折扣應用於原始圖形。如果您添加虛擬節點，它不會導致結果錯誤，甚至任何不同，它只會添加不必要的節點到搜索。

顯然，在路徑輸出中，您應該將任何虛擬節點作爲其原始對象，即A->B'->C的路徑應報告爲A->B->C。

來源

2014-10-08 21:51:15 beaker

我認爲這可以工作。我會在星期一嘗試一下。非常感謝你！ – sandbox 2014-10-10 17:35:24

圖的遍歷算法的折扣

回答

相關問題