关于加权非循环图的代码

Question

我们有一个G(V, E)带有正边和负边​​的加权非循环图代码.我们使用以下代码更改此图形的权重,以给出G无负边缘(G').如果V={1,2...,n}并且G_ij是边缘i到边缘j的权重.

Change_weight(G)
for t=1 to n
   for j=1 to n

      G_i=min G_ij for All K
      if G_i < 0  (we have a bar on G) 
          G_ij = G_ij+G_i  for all j
          G_ki = G_ki+G_i  for all k

我们有两个公理:

1) the shortest path between every two vertex in G is the same as G'.

2)  the length of shortest path between every two vertex in G is the same as G'.

我读了一个低质量的pdf,我不确定准确提到的代码,并添加图片.在这本书中,他说上述公理是错误的,任何人都可以帮助我？我认为这些都是真的吗？

我认为两个是假的,如下面的反例,原始图形在左边给出,并且在算法运行之后,结果在右边,1到3之间的最短路径改变,它从顶点2传递但是在算法运行之后它从未从顶点2传递过.

Answer 1

算法

我对PDF的阅读是:

Change_weight(G)
for i=i to n
   for j=1 to n

      c_i=min c_ij for all j
      if c_i < 0 
          c_ij = c_ij-c_i  for all j
          c_ki = c_ki+c_i  for all k

解释是对于每个顶点,我们通过c_i增加其输出边缘,并且通过c_i减小输入边缘,其中选择c_i使得所有输出边缘变为非负的.

权利要求1

"G中每两个顶点之间的最短路径与G'相同"

通过阅读pdf,这个说法是正确的,因为顶点i和j之间的每条路径都改变了相同的量(c_i-c_j),因此路径的相对顺序不变.(注意,路径可以通过中间顶点,但净效果为0,因为对于每个中间顶点k,我们在输入时减去c_k的长度,但在退出时增加c_k.)

索赔2

"G中每两个顶点之间的最短路径长度与G'相同".

这不可能是真的 - 假设我们从原始图开始,该图具有单个边A到B,权重为-1.在修改后的图表中,此权重将变为0.

因此,最短路径的长度从G中的-1变为G'中的0,因此该语句为假.

例

下面显示的是当您将此算法应用于节点1,然后是节点2时图形会发生什么:

拓扑排序

请注意,如示例中所示,我们仍然会得到一些负面的权重,这可能是无意的.这是因为减少了进入边缘的权重.

但是,如果我们通过图形向后工作(例如,通过使用拓扑排序),那么我们将始终在任何地方都使用非负权重.

在给定的示例中,向后工作意味着我们首先更新2,然后更新1,如下所示: