可能存在负圆时的Floyd-Warshall算法

Question

我正在看Floyd-Warshall algorithm。

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算法是用于寻找最短路径的算法。如果存在负圆，则没有最短路径(您可以找到无限小的(负)路径)。

如果存在负圈，那么会发生什么？我会说Floyd的输出没有任何意义，也就是说，该算法不起作用(既然没有最短路径，那么它怎么起作用呢？)