图论（负权重边） _负权重边

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

– ∞
不小于0。

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

文章图片

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

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

s to c = 5, s→c→d→c=8But s→c is minimumSo s→c = 5

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

s→e = 2, s→e→f→e=-1As -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）=-∞