Let G be a directed weighted graph with n vertices and m edges such that the edges in G have positive weights. Let (u, v

[answerhappygod]

Let G Be A Directed Weighted Graph With N Vertices And M Edges Such That The Edges In G Have Positive Weights Let U V 1 (36.72 KiB) Viewed 32 times

Let G be a directed weighted graph with n vertices and m edges such that the edges in G have positive weights. Let (u, v) be an edge in G. By a shortest cycle containing edge (u, v) we mean a cycle containing (u, v) that is of minimum weight, among all cycles containing (u, v) (if such a cycle exists). Give an O(mlgn)-time algorithm that computes a shortest cycle in G containing the edge (u, v), or reports that no cycle containing edge (u, v) exists.