图论:负权重边

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

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

  1. – ∞
  2. 不小于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)=-∞

负权重边

顶点h, i, g也来自负重量循环。它们也无法从源节点到达, 因此到源的三个节点(h, i, j)的距离为-∞。

微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?