Run Bellman-Ford algorithm, if we find some u,v pair such that d[v] > d[u]+w(u,v). We just need to repeatedly follow the π value until we get back to u.
June 28, 2007
Exercises 24.1-5
Add a new vertex s with new edges (s, v) for every vertex v and cost(s, v) = 0. Apply the Bellman-Ford algorithm to find shortest path from s, then we can find the solution.
Exercises 24.1-4
If some node u,v such that d[u] > d[v] + w(u,v). Then set d[w] = -∞ for all w which there is one path from vu to w.
Exercises 24.1-2
INITIALIZE-SINGLE-SOURCE(G,S) initiates every vertex with infinity. So if there is a path from S to V, the relaxing step would have decreased its d[v] to a value less than infinity.
