Code Output on Graph and some claims on Local Contest?
I ran into a question as follows:
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 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
We have two axioms:
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'.
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?
My Solution:
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. 
Assumptions:
There are a few problems with your presentation of the question; I made some assumptions, which I clarify here. The answer to your question, given that these assumptions are correct, is in the section below.
First , as @amit said, your use of j is not clear. It seems that you meant this:
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
That is, for every vertex i , if the smallest outgoing edge c_i is negative, then increase the weights of all outgoing edges by -c_i and decrease the weights of all incoming edges by -c_i . Then the smallest outgoing edge will have weight of 0.
Second , by itself, this algorithm will not guarantee that G' has no negative edges! Consider the following graph:
Here, the value of edge (1,2) is pushed up to 0 by the operation on 1 , but it is pushed back to -1 by the operation on 2 . You must specify that the graph is in reverse topological order, so that edge (i,j) will always be operated on by j before being operated on by i . (Alternatively, you could sort it in topological order and iterate from n to 1 .)
Answer to your question:
1) The shortest path between every two vertices in G is the same as in G' .
This is true. Consider a path not as a tuple of edges but as a tuple of nodes. For vertices s and t , a path is a tuple of nodes (s, v_1, v_2, ..., t) where there is an edge between every two subsequent elements. For every vertex u , u decreased the cost of incoming edges at the same rate that it increased the cost of outgoing edges; therefore, the relative cost of including u in the path is unchanged.
2) The weight of the shortest path between every two vertices in G is the same as in G' .
This is false. The source s increases its outgoing weight by -c_s , while the destination t decreases its incoming weight by -c_t . If c_s != c_t , then the weight of the path will not be the same.
To reiterate, the weight of every path from s to t will be increased by (c_t-c_s) . Therefore, the shortest path for a given s and t pair will still be the shortest (since all paths between this pair change by the same amount). However, the weight will obviously not necessarily be the same.
上一篇: 最小生成树与最短路径树
下一篇: 图上的代码输出和本地比赛的一些声明？