Claims on shortest path between two node in graph?

 

if the shortest path between two vertex on weighted and directed graph G (maybe has negative edge), is shown by D(u, v) , the following claims is always false.

with having negative edges, but didn't have any negative cycle, then Sigma on D(u,v) (sum on all vertex pairs) cannot be negative. 

Why this claims is False?

what is D(u,v) where there's no path from u to v is not given in my notes, but I think D(u,v)=0 in this case.

Assuming D(u,v) = infinity if there is no path from u to v (I really see no reason to assume otherwise, it is weird to assume D(u,v)=0 in this case), the claim is true.

Proof:

First, assume there is a path for each pair u,v - otherwise sum of all pairs is infinity, and we are done.

For each pair of vertices u,v :

  • If D(u,v)>0 and D(v,u)>0 this pair contribute positive number to the summation
  • Otherwise, and without loss of generality, assume D(u,v)<0 . Since there are no negative cycles, D(u,v) + D(v,u) >= 0 and thus D(v,u) >= -D(u,v) . And as we see, D(v,u) + D(u,v) contribute a non negative number for the summation.

    • Since the above is true for each pair u,v - there is no pair that can contribute a negative number, and the summation cannot be negative.

    QED

    with having negative edges, but didn't have any negative cycle, then Sigma on D(u,v) (sum on all vertex pairs) cannot be negative.

  • D(u, v) = 0 for no arc u -> v

    • Consider the directed graph: 

    1 -> 2 -> 3

    With each arc having cost -1 : there is no negative cost cycle, but the sum over all pairs is negative. So the claim is false because we have found a counterexample.

  • D(u, v) = infinity for no arc u -> v

    • In this case, if we want to find a counterexample we must consider a graph that has paths between all pairs of nodes, otherwise the sum will always be positive because we will be adding an infinite quantity.

    Consider a path with negative cost from a node x to a node y . Then the cost of the path from y to x must be positive and such that D(x, y) + D(y, x) is not negative, otherwise we'd have a negative cycle, which isn't allowed.

    Since each negative cost path must have a positive cost (return path + initial path), the statement is true for this case.

    链接地址: http://www.djcxy.com/p/35266.html

    上一篇: 图上的代码输出和本地比赛的一些声明？

    下一篇: 图中两个节点之间的最短路径的索赔？