图上的代码输出和本地比赛的一些声明？
我碰到一个问题如下：
我们有一个具有正边和负边的加权非循环图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传递。 
假设：
你提出这个问题有几个问题; 我做了一些假设，我在这里澄清。 考虑到这些假设是正确的，你的问题的答案在下面的部分。
首先 ，正如@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，但通过2上的操作推回到-1。 必须指定图形处于逆向拓扑顺序，以便边缘(i,j)在由i操作之前始终由j操作。 （或者，您可以按照拓扑顺序对其进行排序，并从n to 1重复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对的最短路径仍然是最短的（因为该对之间的所有路径改变相同的量）。 但是，重量显然不一定相同。