Home /
Expert Answers /
Computer Science /
2-non-phd-session-only-let-d-v-a-be-a-directed-graph-with-a-distinguished-source-node-s-an-pa530
(Solved): 2. [Non-PhD Session only] Let D = (V, A) be a directed graph with a distinguished source node s an ...
![2. [Non-PhD Session only] Let D = (V, A) be a directed graph with a distinguished source node
s and sink node t. Suppose that](https://media.cheggcdn.com/media/b9b/b9bb8262-6f85-4c80-82c0-e706fd47838c/phpHWptBP)
2. [Non-PhD Session only] Let D = (V, A) be a directed graph with a distinguished source node s and sink node t. Suppose that every edge a € A has a possibly negative length (a). Show that a shortest trail (i.e. a walk without repeating edges) from s to t can be found in polynomial time.
Expert Answer
ANSWER : Let G denote a graph, let w(xy) It denotes the weight of edge xy and lets uv denote the unique edge in G with negative weight. Remove edge uv from G and let G 0 denote the resulting graph. Note that G 0 has no negative length edges. For any