图论：负权重边

它是一张加权图, 其中边缘的总权重为负。如果图具有负边缘, 则它会产生一条链。在执行链之后, 如果输出为负, 则它将赋予-∞权重, 并且条件将被丢弃。如果权重小于负且为-∞, 那么我们就不可能有最短路径。

简而言之, 如果输出为-ve, 则两个条件都将被丢弃。

– ∞
不小于0。

而且我们不可能有最短的路径。

例：

Beginning from s
Adj [s] = [a, c, e]
Weight from s to a is 3

假设我们要计算从s→c的路径。所以我们有2条路径/权重

s to c = 5, s→c→d→c=8
But s→c is minimum
So s→c = 5

假设我们要计算从s→e的路径。所以我们又有两条路

s→e = 2, s→e→f→e=-1
As -1 < 0 ∴ Condition gets discarded. If we execute this chain, we will get - ∞. So we can't get the shortest path ∴ e = ∞.

此图说明负权重和负权重循环对最短路径权重的影响。

因为只有一条路径从“ s到a”（路径<s, a>）, 所以δ（s, a）= w（s, a）= 3。

此外, 从“ s到b”只有一条路径, 因此δ（s, b）= w（s, a）+ w（a, b）= 3 +（-4）=-1。

从“ s到c”有无限多的路径：<s, c>：<s, c, d, c>, <s, c, d, c, d, c>等。因为循环<c, d, c>的权重为δ（c, d）= w（c, d）+ w（d, c）= 6 +（-3）= 3, 大于0, 最短从s到c的路径是<s, c>, 权重δ（s, c）= 5。

同样, 从“ s到d”的最短路径是<s, c, d>, 权重δ（s, d）= w（s, c）+ w（s, d）= 11。

类似地, 从s到e有无数的路径：<s, e>, <s, e, f, e>, <s, e, f, e, f, e>, 依此类推。由于周期<e, f, e>的权重为δ（e, f）= w（e, f）+ w（f, e）= 3 +（-6）= -3。因此-3 <0, 但是从s到e没有最短的路径。 B8y遍历负权重循环<e, f, e>。这意味着从s到e的路径具有任意大的负权重, 因此δ（s, e）=-∞。

类似地, 由于从f可以到达g, 因此δ（s, f）=-∞, 我们还可以找到一条从s到g具有任意大的负权重的路径, 而δ（s, g）=-∞