Dijkstra在網絡圖建模上的算法

我們有一個針對通信的有向圖G = (V, E)。網絡，每個邊緣的概率不存在於區間[0,1]內的r(u, v)（定義爲邊緣權重）。概率是獨立的，所以從一個頂點到另一個頂點，如果我們乘以所有的概率，我們就可以得到整個路徑不失敗的概率。我需要一個有效的算法來找到從一個給定頂點到另一個給定頂點（即，從第一個頂點到第二個最不可能失敗的路徑）的最可靠路徑。我認爲log(r · s) = log r + log s會有所幫助。Dijkstra在網絡圖建模上的算法

這是我迄今爲止 - ：

DIJKSTRA-VARIANT (G, s, t) 
for v in V: 
    val[v] ← ∞ 
A ← ∅ 
Q ← V to initialize Q with vertices in V. 
val[s] ← 0 
while Q is not ∅ and t is not in A 
    do x ← EXTRACT-MIN (Q) 
    A ← A ∪ {x} 
    for each vertex y ∈ Adj[x] 
     do if val[x] + p(x, y) < val[y]: 
      val[y] = val[x] + p(x, y)

s是源頂點和t是目標頂點。當然，我還沒有利用log屬性，因爲我無法理解如何使用它。需要修改底部算法的部分弛豫，並且val數組將捕獲結果。沒有日誌，它可能會存儲下一個最高的概率。我應該如何修改算法以使用log？

來源

2014-02-16 PritishC

你對Dijkstra有多瞭解？你知道它解決了什麼問題嗎？你是否看到了這個問題和你給出的問題之間的區別？ *現在*您是否看到日誌屬性可能有用？ – Beta

1.「你對Dijkstra的理解程度如何？」 - 一點點。 2.「你知道它解決了什麼問題嗎？」 - 它解決了尋找單一來源的最短路徑的問題。 3.「問題之間有什麼區別？」 - 邊權重是在[0，1]範圍內的概率。要找到從一個頂點到另一個頂點的最可靠路徑，我必須乘以概率並獲得最高路徑。 4.「你看到'log'可以用來做什麼嗎？」 - 這是我不明白。 – PritishC

哦，等等...因爲我必須乘以概率，我應該使用'log'來保持總和嗎？ – PritishC

現在，你的代碼有

do if val[x] + p(x, y) < val[y]: 
    val[y] = val[x] + p(x, y)

因爲在這種情況下，邊權表示概率，你需要一起乘他們（而不是增加）：

do if val[x] * p(x, y) > val[y]: 
    val[y] = val[x] * p(x, y)

我已經改變因爲您希望概率儘可能大，所以標記爲>。

日誌是有用的，因爲（1）log(xy) = log(x) + log(y)（如你所說）和資金更容易計算不是產品，和（2）log(x)是x單調函數，所以log(x)和x有他們在同一個地方最大。因此，你可以處理的可能性的對數，而不是概率本身：

do if log_val[x] + log(p(x, y)) > log_val[y]: 
    log_val[y] = log_val[x] + log(p(x, y))

編輯補充（因爲我沒有足夠的代表處發表評論）：你要初始化val數組到0，而不是Infinity，因爲您正在計算最大值而不是最小值。（因爲您希望最大概率而不是失敗。）所以，日誌轉換後，初始log_val數組值應爲-Infinity。

來源

2014-02-16 08:23:19 tinybike

爲了方便起見，我可以在算法中使用'-Infinity'嗎？ – PritishC

是的 - 只是改變初始'val [v] = -Infinity'，用'log（p（x，y））'代替'p（x，y）'，並且改變'<' to a '>'和你應該很好走。而且，我想我可能剛剛完成了你的家庭作業，但是哦:) – tinybike

嗯，至少我嘗試過，不像大多數其他人。我相信'val [s]'應該是1，並且在應用'log'的時候我會得到0.我說1，因爲頂點's'已經在包中，並且1代表可能性最高的概率。這與Dijkstra的正常實現中的0類似。 – PritishC

爲了計算應該在鬆弛階段，乘（而不是添加）的概率，其意味着改變：

do if val[x] + p(x, y) < val[y]: 
      val[y] = val[x] + p(x, y)

到：

do if val[x] * p(x, y) < val[y]: 
      val[y] = val[x] * p(x, y)

使用日誌是可能的，如果範圍因爲log（0）= -infinity且log（1）= 0，這意味着每x,y in (0,1]：
probability x < probability y比：
log(x) < log(y)。
由於我們保持t他相同的關係（概率之間）這種修改將提供正確的答案。

我想你可以從這裏拿它。

來源

2014-02-16 08:21:03 alfasin

我想我可能已經部分解決了這個問題。

這是我的嘗試。編輯和指針歡迎 - ：

DIJKSTRA-VARIANT (G, s, t) 
for v in V: 
    val[v] ← 0 
A ← ∅ 
Q ← V to initialize Q with vertices in V. 
val[s] ← 1 
while Q is not ∅ and t is not in A 
    do x ← EXTRACT-MAX (Q) 
    A ← A ∪ {x} 
    for each vertex y ∈ Adj[x] 
     do if log(val[x]) + log(p(x, y)) > log(val[y]): 
      log(val[y]) = log(val[x]) + log(p(x, y))

既然我找到儘可能高的概率值，我相信我應該使用>。下面的問題依然存在 - ：

應該採取什麼val數組中的初始值是什麼？
還有什麼我需要補充的嗎？

編輯：我已經改變了初始val值0。但是，log爲0是不明確的，我開到一個更好的選擇。此外，我將優先級隊列的方法更改爲EXTRACT-MAX，因爲它是需要提取的較大概率。理想情況下，這將在binary max-heap上執行。

進一步編輯：我已經標記tinybike的答案被接受，因爲他們張貼了我需要的大部分必要的細節。該算法應該像我在這裏發佈的一樣。

來源

2014-02-16 08:24:19 PritishC

Dijkstra在網絡圖建模上的算法

回答

相關問題