Let G(V, E) be a graph with positive and negative weights on its edges, but with

Question

Let G(V, E) be a graph with positive and negative weights on its edges, but with no negative cycles. Let s elementof V. Assume it is known that for every shortest path between every pair of nodes, the number of edges in the path is at most k, but k is not known to you. Suggest a modification of Bellman-Ford algorithm so the running time of the new algorithm is O(km). Prove that your algorithm still finds the shortest path from s to every other node, and the correctness of the bound you provided for the running time. As usual n = |v|, and m = |E|.

Explanation / Answer

Modified Bellman-Ford Algorithm

----------------------------------------------------

1) Initialize distances from source s to all vertices as infinite and distance to source itself as 0, d(s)=0.

2) Do the following n-1 times

.....a) change_in_distance = false.
…..b) for each edge u-v
………………If d[v] > d[u] + weight of edge uv, then update d[v]
………………….d[v] = d[u] + weight of edge uv

...........................change_in_distance = true

......c) if change_in_distance == false

..................break outer loop.

The above algortihm works as below

-------------------------------------------------------

It first calculates the shortest distances for the shortest paths which have at-most one edge in the path. Then, it calculates shortest paths with at most 2 edges, and so on. After the ith iteration of outer loop, the shortest paths with at most i edges are calculated. Since at most n-1 can be there in any simple path the outer loop runs n-1 times. If in any subsequent iteration none of the vertex distances changes then it means we found all the shortest paths(means we reached iteration k) so the loop breaks.

Running time

-----------------------

The running time depends on the number of times the outer loop runs, from the problem statement it cannot run more than k times since all shortest path will be found in or before kth iteration so the running time is O(km)

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.