algorithm - 負の円が存在する可能性がある場合の Floyd-Warshall アルゴリズム

Question

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これは無効にならないのですか？