使用 Floyd-Warshall 算法找到负权重圆
Use Floyd-Warshall algorithm to find negative-weight circles
判断一个图是否包含负圆，经过运行Floyd-Warshall算法，是否只能通过扫描矩阵的对角线元素来判断是否有负元素来处理问题。不知道怎么证明...
应该清楚的是，如果在算法期间的任何迭代中 M[i][j] 中存在负值，则存在从 i 到 j 的负成本路径。如果M[i][i]<0则存在从i到i的负成本路径，因为它是一条闭合路径，所以它必须包含一个循环。
有两种情况：要么**它**是一个循环，要么你可以在路径中找到一个不同于i的j，
并将路径划分为 p1=path(i,j),2) p2=path(j,j) p3= path (i,j)。所以要么 p2 是一个负封闭路径，要么 p1 union p3 是一个负封闭路径。取一个负数并应用相同的参数直到你得到一个循环，它必须是负数
相反，如果有一个负循环 'C' 由节点子集 S 和边总和 T 组成，包含一些节点 i 然后在迭代其中FW经过了S中的所有节点，M[i][i]的值至少要和'C'的路径成本一样小，所以M[i][i]<=T<0。由于 FW 是非递增的，M[i][i] 在算法结束之前保持负值。
判断一个图是否包含负圆，经过运行Floyd-Warshall算法，是否只能通过扫描矩阵的对角线元素来判断是否有负元素来处理问题。不知道怎么证明...
应该清楚的是，如果在算法期间的任何迭代中 M[i][j] 中存在负值，则存在从 i 到 j 的负成本路径。如果M[i][i]<0则存在从i到i的负成本路径，因为它是一条闭合路径，所以它必须包含一个循环。
有两种情况：要么**它**是一个循环，要么你可以在路径中找到一个不同于i的j，
并将路径划分为 p1=path(i,j),2) p2=path(j,j) p3= path (i,j)。所以要么 p2 是一个负封闭路径，要么 p1 union p3 是一个负封闭路径。取一个负数并应用相同的参数直到你得到一个循环，它必须是负数
相反，如果有一个负循环 'C' 由节点子集 S 和边总和 T 组成，包含一些节点 i 然后在迭代其中FW经过了S中的所有节点，M[i][i]的值至少要和'C'的路径成本一样小，所以M[i][i]<=T<0。由于 FW 是非递增的，M[i][i] 在算法结束之前保持负值。