小编Anj*_*ark的帖子

我遇到了如下问题:

我们有一个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传递过.