加权无环图代码

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

"the shortest path between every two vertex in G is the same as G'"

根据我对 pdf 的阅读，这种说法是正确的，因为顶点 i 和 j 之间的每条路径都改变了相同的量 (c_i-c_j)，因此路径的相对顺序没有改变。（请注意，路径可能经过中间顶点，但净效应为 0，因为对于每个中间顶点 k，我们在进入时将长度减少 c_k，但在退出时增加 c_k。）

声明 2

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

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

因此最短路径的长度从G中的-1变成了G'中的0所以这个说法是错误的。

例子

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

拓扑排序

请注意，如示例所示，我们最终仍会得到一些负权重，这可能是无意的。这是因为传入边的权重降低了。

但是，如果我们对图进行反向处理（例如通过使用拓扑排序），那么我们将始终以非负权重结束。

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

加权无环图代码

Code on Weighted, Acyclic Graph

algorithm

tree

graph

shortest-path

data-structures

算法

声明 1

声明 2

例子

拓扑排序