c++ - 图上的代码输出和本地竞赛的一些声明？

Question

我遇到了如下问题:

我们有一个带正负边的加权非循环图 G(V, E) 代码。我们用下面的代码改变这个图的权重，得到一个没有负边的 G (G')。如果 V={1,2...,n} 和 G_ij 是边 i 到边 j 的权重。

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

我们有两个公理:

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

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

We want to verify these two sentence. which one is True and Which one is false. Who can add some hint why these are true or false?

我的解决方案:

我认为两个是假的，因为下面的反例，原始图在左边给出，算法运行后，结果在右边，1到3之间的最短路径发生了变化，它从顶点2传递但是在算法运行它从未从顶点 2 传递。

Answer 1

假设:

您对问题的陈述存在一些问题；我做了一些假设，我在这里澄清一下。鉴于这些假设是正确的，您的问题的答案在下面的部分中。

首先，正如@amit 所说，您对j 的使用不清楚。看来你的意思是:

Change_weight(G)
  for i = 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

即对于每个顶点i，如果最小出边c_i为负，则将所有出边的权重增加-c_i 并通过 -c_i 减少所有传入边的权重。那么最小的出边将具有 0 的权重。

其次，此算法本身不能保证G' 没有负边!考虑下图:

这里边(1,2)的值被1上的操作推到0，但是又被操作推回-1在 2 上。您必须指定图的拓扑顺序相反，以便边 (i,j) 在被 i 操作之前总是被 j 操作。 (或者，您可以按拓扑顺序对其进行排序，然后从 n 到 1 进行迭代。)

---

您问题的答案:

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

这是真的。将路径视为节点元组而不是边元组。对于顶点 s 和 t，路径是节点 (s, v_1, v_2, ..., t) 的元组，其中有每两个后续元素之间的边缘。对于每个顶点 u，u 以与增加传出边成本相同的速率降低传入边的成本；因此，在路径中包含 u 的相对成本是不变的。

2) G中每两个顶点之间的最短路径的权重与G'中的相同。

这是错误的。源 s 将其输出权重增加 -c_s，而目标 t 将其输入权重减少 -c_t .如果c_s != c_t，那么路径的权重就不会相同。

重申一下，从s到t的每条路径的权重都会增加(c_t-c_s)。因此，给定的 s 和 t 对的最短路径仍然是最短的(因为这对之间的所有路径变化量相同)。但是，权重显然不一定相同。