负权回路(Negative Weight Cycle)是图中存在至少一个环,使得经过该环的路径权重之和为负值。在带权图中,每条边都有一个权值,而负权回路是指一个环中所有边的权值之和为负数。
具体而言,如果一个有向图或无向图中存在一个环,使得环中的边权重之和为负值,那么这个环就被称为负权回路。
负权回路的存在可能导致在求解最短路径的过程中出现问题。例如,对于一般的最短路径算法(如 Dijkstra 或 Bellman-Ford 算法),它们无法处理图中存在负权回路的情况,因为在存在负权回路的图中,最短路径可能是无限小的。
在某些情况下,我们需要注意负权回路的存在,因为它可能导致算法无法给出正确的结果。在应用最短路径算法时,通常会先检查图中是否存在负权回路,以确保算法的正确性。