Here is a suggested algorithm for finding a shortest path from a vertex s to a v

Question

Here is a suggested algorithm for finding a shortest path from a vertex s to a vertex t in a directed graph G with both positive and negative edge weights but no negative cycle:

1. Add a large constant to each edge weight so that all edge weights become positive.

2. Run Dijkstra’s algorithm starting at node s and return the shortest path found to vertex t.

Either prove that the suggested algorithm works correctly, or give a counterexample.

(For proving algorithm works correctly, show psuedocode and state why it works.)

Explanation / Answer

S=<s> Q=<y,t,x,z>

S=<s,y> Q=<z,t,x>

S=<s,y,z> Q=<t,x>

S=<s,y,z,t> Q=<x>

no enough place to display one more image so i given final output

S=<s,y,z,t,x> Q=<>

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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