Page 1 of 1
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
Posted: Mon Jun 06, 2022 6:33 pm
by 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 22 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.