加权无环图上的编码

Question

加权无环图上的编码

algorithmdata-structuresgraphtreeshortest-path

3

我们有一份关于加权无环图 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。

- user4554402

你的修改后的图中从顶点1到2的长度是多少？（在图片中看起来像“v”）我认为应该是-1（从1开始，增加2，减少4），因此我认为最短路径没有改变。 - Peter de Rivaz

亲爱的@PeterdeRivaz，也许代码不够易读？也许？ - user4554402

确实，这很难理解，因此很难确定。 - Peter de Rivaz

在我看来，你在反例中错误地修改了边缘，因此我仍然认为第一个公理是错误的，而第二个是正确的。然而，由于PDF质量很低，我建议你尝试寻找其他信息来源 - 我推荐使用Python Networkx库，其中包含许多已实现的良好算法，包括最短路径算法。 - Peter de Rivaz

请您更新我的反例？ - user4554402

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter de Rivaz · Accepted Answer

算法

我的阅读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，如下所示：