code加权，无环图 [英] Code on Weighted, Acyclic Graph

问题描述

我们有一个code加权，无环图 G（V，E）有正面和负面的边缘。我们改变这个图的重量以下code，给予无下降沿（G'）。如果 V = {1,2，...，N} 和 G_ij 是我边到边j的权重

We have a Code on Weighted, Acyclic Graph G(V, E) with positive and negative edges. we change the weight of this graph with following code, to give a G without negative edge (G'). if V={1,2...,n} and G_ij be a weight of edge i to edge 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具有低质量的，我不知道该code正好提到，并添加图片。在这本书中，他说上面的公理是假的，任何人都可以帮助我吗？我觉得这些都是真的吗？

i read one pdf that has low quality, i'm not sure the code exactly mentioned, and add the picture. in this book he say the above axioms is false, anyone could help me? i think these are true?

我认为2是假如以下反例，原来的图表中给出左，算法运行后，其结果是在右之间1〜3中的最短路径改变时，它从顶点2，但之后的传递算法运行它永远不会从顶点2通过。

i think two is false as following counter example, the original graph is given in left, and after the algorithm is run, the result is in right the shortest path between 1 to 3 changed, it passed from vertex 2 but after the algorithm is run it never passed from vertex 2.

推荐答案

我的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

间pretation是，对于每个顶点我们增加其出边由C_I，和由C_I，其中C_I被选择为使得所有传出的边缘成为非负降低进入边缘。

The interpretation is that for each vertex we increase its outgoing edges by c_i, and decrease the incoming edges by c_i, where c_i is chosen such that all outgoing edges become non-negative.

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

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

通过我的读数的PDF的，这种说法是正确的，因为顶点之间的每个路径i和j相同的量（C_I-c_j）等的路径的相对顺序是不变的被改变。 （注意，路径可以经由中间顶点去，但净效果是0，因为对于每一个中间顶点ķ进入时我们减小长度由C_K，但通过退出时C_K增加。）

With my reading of the pdf, this claim is true because every path between vertices i and j is changed by the same amount (c_i-c_j) and so the relative order of paths is unchanged. (Note that the path may go via intermediate vertices, but the net effect is 0 because for each intermediate vertex k we decrease the length by c_k when entering, but increase by c_k when exiting.)

每两顶点G中之间最短路径的长度是相同的G'

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

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

This cannot be true - suppose we start with an original graph which has a single edge A to B with weight -1. In the modified graph this weight will become 0.

因此​​，最短路径的长度已经从-1改为G中以0 G'这样的说法是错误的。

Therefore the length of the shortest path has changed from -1 in G to 0 in G' so the statement is false.

下面显示的是会发生什么样的图形，你应用这个算法，节点1，其次为节点2：

Shown below is what would happen to your graph as you applied this algorithm to node 1, followed by node 2:

需要注意的是如图所示的例子中，我们还是结束了一些负面的权重这可能是无意的。这是因为进入的边缘的权重减小。

Note that as shown in the example, we still end up with some negative weights which is probably unintended. This is because the weights of incoming edges are reduced.

不过，如果我们倒退工作，通过图（用拓扑排序EG），那么我们将永远结束​​了非负权重无处不在。

However, if we work backwards through the graph (e.g. by using a topological sort), then we will always end up with non-negative weights everywhere.

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

In the given example, working backwards means we first update 2, and then 1 as shown below:

这篇关于code加权，无环图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！