干杯，我正在嘗試解決有向圖中的最小長度回圈問題，我遇到了一個解決方案，建議我應該調整 Floyd-Warshall 演算法來解決這個問題。它說path[i][i] = 0我應該設定而不是設定path[i][i] = INFINITY，但我不完全理解為什么會這樣！我發現 Floyd-Warshall 使用的陣列的主對角線沒有變化，那么它如何幫助我看到回圈的路徑？我了解生成的演算法陣列可以幫助我找到一對中的最短路徑。egpath[i][j]給了我從i到j的最短路徑，但是，雖然直覺保持不變，但我看到沒有任何變化，我無法得到想要的結果。
我什至嘗試可視化這個程序，在這里使用這個網站，我生成了一個包含許多回圈的圖形，但是雖然對角線被初始化為無窮大，但它并沒有改變。誰能解釋我錯過了什么或我能做些什么來解決我的問題？
uj5u.com熱心網友回復：
對于有向圖，想法是您只是更改矩陣，以便存盤最短非空path路徑的長度，而不是存盤最短路徑的長度 from ito j，即，它僅包含至少一個路徑邊緣。當然，這只影響從頂點到自身的路徑。path[i][j]
所以現在，我們path[i][i]用infinity0 而不是 0 進行初始化，因為那時我們還沒有找到從頂點到自身的任何非空路徑。
然后，在根據邊初始化矩陣的其余部分后，我們進行正常的 Floyd-Warshall 迭代：
for k in |V|:
for j in |V|:
for i in |V|:
path[i][j] = min(path[i][j], path[i][k] path[k][j])
假設有一個簡單的回圈 1 -> 2 -> 1。然后，當 時(i,j,k) == (1,1,2)，我們做path[1][1] = min(path[1][1], path[1][2] path[2][1])
這path[1][1]從infinity到回圈長度。
如果您修改了一個實作但它沒有這樣做，那么該實作可能已被優化為完全忽略對角線。
uj5u.com熱心網友回復：
影片網站的 Floyd-Warshall 演算法編碼方式有一個實作細節；它會阻止您看到您期望的結果。
下載源代碼并查看Floyd.js不應該存在的條件：
for (var k = 0; k < this.size; k ) {
for (var i = 0; i < this.size; i ) {
for (var j = 0; j < this.size; j ) {
if (i != j && j != k && i != k) // <<== This is the problem
...
該演算法從不計算從一個節點i == j通過第三個節點到其自身的路徑（即何時），因此它從不檢測回圈。本質上，該條件假設無法改進對自身的傳遞，這在主對角線設定為 的情況下是不正確的INFINITY。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/466750.html