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无效吗？

Answer 1

Floyd-Warshall 算法用于寻找最短路径。如果存在负圆，则没有最短路径（您可以找到无限小（负）路径）。

如果负圈存在，会发生什么？我会说弗洛伊德的输出没有任何意义，也就是说，那个算法不起作用（因为没有最短路径，它怎么能起作用？）。