graph-theory - 使用 Floyd-Warshall 算法找到负权重的圆

Question

要判断一个图是否包含负圆，在运行Floyd-Warshall算法后，是否可以只通过扫描矩阵的对角元素来判断它是否有负元素来处理这个问题。不知道怎么证明...

Answer 1

应该清楚的是，如果在算法期间的任何迭代中存在负值，则存在从到M[i][j]的具有负成本的路径。如果从到有一条负成本路径，因为它是一条封闭路径，它必须包含一个循环。ijM[i][i]<0ii

有两种情况：要么 **it ** 是一个循环，要么你可以在路径中找到一个j不同的 from i，并将路径划分为p1=path(i,j),2) p2=path(j,j) p3= path (i,j). 所以要么p2是负闭合路径，要么p1联合p3是负闭合路径。取一个负数并应用相同的论点，直到你得到一个循环，它必须是负数

S相反，如果存在由具有边总和 的节点子集形成的负循环“C” T，包含某个节点i，则在 FW 已通过 中的所有节点的迭代中S， 的值M[i][i]必须至少与路径“C”的成本如此M[i][i]<=T<0。由于 FW 不增加，M[i][i]因此在算法结束之前保持负数。