查找具有加權頂點的圖形路徑

Question

我有以下圖形，其中每個頂點具有關聯的「概率」 （graph with weighted nodes）。

我想找到從節點0到最後一個節點（指數最高，這裏5），具有最高概率相乘的路徑。在這個圖中，最佳路徑是0-1-4-5，這給出了0.72的概率。

我曾經想過使用BFS來查找開始和結束節點之間的所有路徑，然後將每個節點的概率相乘，但我認爲這對於所有圖形都有效。我怎麼能用python解決這個問題？

Answer 1

正如朱利安建議，Dijkstra's algorithm將是一個很好的開始。你的問題和正常的Dijkstra之間有兩點區別。

1. Dijkstra的算法最小化權重的總和。爲了使概率的乘積最大化，可以將每個權重p映射到-log(p)。快速證明：最大化(x1*x2*...*xn)的產品與最大化log(x1*x2*...*xn)相同，因爲log是monotonically increasing。 argmax(log(x1*x2*...*xn)) = argmax(log(x1)+log(x2)+...+log(xn)) = argmin(-log(x1)-log(x2)-...-log(xn)))。請注意，如果你想要得到的概率，你可以通過採用10^(-c)來反轉結果，其中c是Dijkstra使用上述減少（假設你以10爲底的日誌）返回的最小成本。另請注意，如果任何概率爲0，則log(0)未定義，因此您應該通過使權重無限（因此路徑永遠不會經過該節點）來處理此問題。

2. Dijkstra's使用加權邊緣，而您有加權節點。但它是從加權節點到加權邊的簡單縮減。定義從u到v與edge_weight(u,v) = vertex_weight(v)的邊的權重。根據你的圖片判斷，你有一個無向圖，所以你需要用兩個有向邊替換每個無向邊，使用與上述相同的權重（注意，兩個頂點u和v之間的兩個邊將具有不同的權重，除非vertex_weight(u) == vertex_weight(v)）。另外，如果您想返回最短路徑的值，則需要將vertex_weight(source_vertex)添加到最終成本中，因爲此成本在減少中將被跳過。