Given a graph of all negative edge weights: Design an algorithm that could he us

Question

Given a graph of all negative edge weights: Design an algorithm that could he used to determine the largest weight paths starting from a particular vertex (i.e.. the source vertex) to each of the either vertices in the graph. The largest weight path from a source vertex s to a target vertex d is the path with the largest sum of the negative edge weights (i.e., smaller value for the absolute sum). What is the time complexity of your algorithm? For the following graph, assign negative weights of your choice (in the range -10 ... -1) to the edges and determine the largest weight path starting from a vertex of your choice. Clearly indicate the chosen edge weights and the chosen starting vertex (i.e.. the source vertex). Show all the steps.

Explanation / Answer

Problem is equivalent to finding shortest path from source to all destinations. This is a standard problem solved by Dijkstra's algorithm. Dijkstra finds shortest path from source to all destinations which is same as finding largest path if weights are negative.
Dijkstra's algo runs in O(E log V) if binary heap is used.
Algo: keep an array spT of vertices that've been visited and shortest distance found from source has been finalized. Pick a vertex which is not in spT which has min distance value (i.e min distance from source) and update all it's neighbour's v distance values if existing distance value is higher than distanceV[u] + edge[u-v].
This iteration is relaxing distance values of vertices through it's neighbour which already has min distance value from source, so this current vertex will also have min value.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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