Negative Cycle

定义 Definition

negative cycle（负权环/负环）：在带权图中，一个环路上所有边的权重之和为负数的循环路径。它常见于最短路径问题中：如果从某个起点可达负权环，那么“最短路径”可能不存在（因为可以无限次绕环让路径代价越来越小）。

例句 Examples

A negative cycle makes the shortest path undefined.
负权环会使最短路径变得没有定义（不存在有限的最短值）。

When the BellmanFord algorithm detects a negative cycle reachable from the source, it reports that distances can be decreased indefinitely.
当 BellmanFord 算法检测到从源点可达的负权环时，它会报告距离可以被无限降低。

发音 Pronunciation

/ntv sakl/

词源 Etymology

negative 源自拉丁语 negativus（表示否定的）；cycle 源自希腊语 kyklos（圆、轮、循环）。合在一起在图论与算法语境中指“总权重为负的循环结构”，因此中文常译为“负权环/负环”。

相关词 Related Words

• Bellman-Ford
• Shortest Path
• Weighted Graph
• Cycle
• Negative Edge
• Floyd-Warshall
• Graph Theory

文学与经典著作中的用例 Literary Works

• Introduction to Algorithms（《算法导论》, Cormen/Leiserson/Rivest/Stein）：在最短路径章节讨论 negative-weight cycle / negative cycle 及其对最短路定义的影响。
• Algorithm Design（《算法设计》, Kleinberg & Tardos）：讲解最短路径与 BellmanFord 时提及负权环检测。
• The Algorithm Design Manual（《算法设计手册》, Steven S. Skiena）：在图算法与最短路径部分介绍负权边与负环带来的问题与处理方式。