Graph Theory Let G V E be directed weighted graph with exac

Graph Theory.

Let G = (V, E) be directed, weighted graph with exactly one negative weight edge, but no negative weight cycles. Give an efficient algorithm to solve the single source shortest path problem. Analyze it execution time. Informally justify the correctness of your algorithm.

Solution

BELLMAN-FORD algorithm can be used to find the single source shortest path problem when the graph is directed and it has negative edges.

the algorithm is as follows:

The execution time of this algorithm is: O(|V|.|E|)

where V is the number of vertices and E is the number of edges in the graph.

Proof of Correctness of algorithm:

The correctness of the algorithm can be shown by induction.

The precise statement shown by induction is:

Lemma. After i repetitions of for loop:

Proof. For the base case of induction, consider i=0 and the moment before for loop is executed for the first time. Then, for the source vertex, source.distance = 0, which is correct. For other vertices u, u.distance = infinity, which is also correct because there is no path from source to u with 0 edges.

For the inductive case, we first prove the first part. Consider a moment when a vertex\'s distance is updated by v.distance := u.distance + uv.weight. By inductive assumption, u.distance is the length of some path from source to u. Then u.distance + uv.weight is the length of the path from source to v that follows the path from source to u and then goes to v.

For the second part, consider the shortest path from source to u with at most i edges. Let v be the last vertex before u on this path. Then, the part of the path from source to v is the shortest path from source to v with at most i-1 edges. By inductive assumption, v.distance after i1 iterations is at most the length of this path. Therefore, uv.weight + v.distance is at most the length of the path from s to u. In the i^th iteration, u.distance gets compared with uv.weight + v.distance, and is set equal to it if uv.weight + v.distance was smaller. Therefore, after i iteration, u.distance is at most the length of the shortest path from source to u that uses at most i edges.

If there are no negative-weight cycles, then every shortest path visits each vertex at most once, so at step 3 no further improvements can be made. Conversely, suppose no improvement can be made. Then for any cycle with vertices v[0], ..., v[k1],

v[i].distance <= v[i-1 (mod k)].distance + v[i-1 (mod k)]v[i].weight

Summing around the cycle, the v[i].distance and v[i1 (mod k)].distance terms cancel, leaving

0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight

I.e., every cycle has nonnegative weight.