Code on Weighted, Acyclic Graph

algorithm, data-structures, graph, shortest-path, tree

Solution

Algorithm

My reading of the PDF is:

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

The interpretation is that for each vertex we increase its outgoing edges by c_i, and decrease the incoming edges by c_i, where c_i is chosen such that all outgoing edges become non-negative.

Claim 1

"the shortest path between every two vertex in G is the same as G'"

With my reading of the pdf, this claim is true because every path between vertices i and j is changed by the same amount (c_i-c_j) and so the relative order of paths is unchanged. (Note that the path may go via intermediate vertices, but the net effect is 0 because for each intermediate vertex k we decrease the length by c_k when entering, but increase by c_k when exiting.)

Claim 2

"the length of shortest path between every two vertex in G is the same as G'".

This cannot be true - suppose we start with an original graph which has a single edge A to B with weight -1. In the modified graph this weight will become 0.

Therefore the length of the shortest path has changed from -1 in G to 0 in G' so the statement is false.

Example

Shown below is what would happen to your graph as you applied this algorithm to node 1, followed by node 2:

Topological sort

Note that as shown in the example, we still end up with some negative weights which is probably unintended. This is because the weights of incoming edges are reduced.

However, if we work backwards through the graph (e.g. by using a topological sort), then we will always end up with non-negative weights everywhere.

In the given example, working backwards means we first update 2, and then 1 as shown below:

Problem

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 t=1 to n for j=1 to n G_i=min G_ij for All K if G_i < 0 (we have a bar on G) G_ij = G_ij+G_i for all j G_ki = G_ki+G_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'. ``` i read one pdf that has low quality, i'm not sure the code exactly mentioned, and add the picture. in this book he say the above axioms is false, anyone could help me? i think these are true? 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.

Original source