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

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'相同.

我们要验证这两句话.哪一个是真的,哪一个是假的.谁可以添加一些暗示为什么这些是真还是假？

我的解决方案

我认为两个是假的,如下面的反例,原始图形在左边给出,并且在算法运行之后,结果在右边,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'没有负边！考虑下图：

这里，edge 的值(1,2)通过 的操作被推至 0 1，但通过 的操作又被推回到 -1 2。您必须指定该图是逆拓扑顺序的，以便边(i,j)始终先被 操作，j然后再被 操作i。（或者，您可以按拓扑顺序对其进行排序并从 进行迭代n to 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仍然是最短的（因为该对之间的所有路径变化量相同）。然而，重量显然不一定相同。