Floyd-Warshall算法在可能存在負圓的情況下

我正在查看Floyd-Warshall algorithm。Floyd-Warshall算法在可能存在負圓的情況下

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 

// part 1 
for each vertex v 
    dist[v][v] ← 0 

// part 2 
for each edge (u,v) 
    dist[u][v] ← w(u,v) // the weight of the edge (u,v) 

// part 3 
for k from 1 to |V| 
    for i from 1 to |V| 
     for j from 1 to |V| 
     if dist[i][k] + dist[k][j] < dist[i][j] then 
      dist[i][j] ← dist[i][k] + dist[k][j]

在頁面上，它說the Floyd–Warshall algorithm assumes that there are no negative cycles。所以我的問題是如果輸入圖表隱藏負圓將會發生什麼。輸出dist是否代表隱藏負圓的另一個圖形？ part 1是否無效？

來源

2013-06-03 SoftTimur

您讀完維基百科文章的那一部分了嗎？（http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Behavior_with_negative_cycles）。它告訴你如何檢測負循環。 –

是的，我做了（順便說一句，我已經把[另一個問題]（http://stackoverflow.com/questions/16898416/fastest-algorithm-to-detect-if-there-is-negative-circle-in-a-我不希望把'檢測'和'歸一化'放在一起，我希望一個「歸一化」總是成立的：一個負圓的圖減少到另一個負圓的圖 – SoftTimur

但是FW的輸出不是圖形，而是距離矩陣 –

Floyd-Warshall算法用於查找最短路徑。如果存在負圓，則沒有最短路徑（可以找到無限小（負）路徑）。

如果存在負圓，那麼會發生什麼？我會說Floyd的輸出沒有任何意義，也就是說，算法不起作用（因爲沒有最短路徑，它如何工作？）。

來源

2013-06-03 14:59:39

但是整體使用FW的對比例如Dijkstra是它能夠檢測** negativ e週期。 –

bellman-ford can ... – 2013-06-03 15:13:09

啊，你是對的！我得到我的「X-Y」圖算法困惑... –

Floyd-Warshall算法在可能存在負圓的情況下

回答

相關問題