# Question

Professor Green street claims that there is a simpler way to re-weight edges than the method used in Johnson's algorithm. Letting w* = min (u, v)E {w(u, v)}, just define w(u, v) = w(u, v) - w* for all edges (u, v) E. What is wrong with the professor's method of reweighing?

## Answer to relevant Questions

Professor Michener claims that there is no need to create a new source vertex in line 1 of JOHNSON. He claims that instead we can just use G′ = G and let s be any vertex in V [G]. Give an example of a weighted, ...Prove that for any pair of vertices u and v and any capacity and flow functions c and f, we have cf (u, v) + cf (v, u) = c(u, v) + c(v, u).A path cover of a directed graph G = (V, E) is a set P of vertex-disjoint paths such that every vertex in V is included in exactly one path in P. Paths may start and end anywhere, and they may be of any length, including 0. ...Show that the depth of SORTER [n] is exactly (lg n) (lg n + 1)/2.Give an algorithm that determines whether or not a given undirected graph G = (V, E) contains a cycle. Your algorithm should run in O (V) time, independent of |E|.Post your question

0