= Shortest cycle by repeated shortest-path trees
In a positive-weight <directed graph>, run the <Dijkstra algorithm> from each source $s$ and minimize $d_s(u)+w(u,s)$ over closing <edges>. In an <undirected graph>, minimize $d_s(u)+w(u,v)+d_s(v)$ only over <edges> absent from the current <shortest-path tree>. A <tree> <edge> would otherwise give a spurious traversal out and back. A non-tree candidate contains a genuine cycle no longer than its score, even when the two <tree> routes share a prefix.
For the undirected optimum, choose a shortest cycle and a source on it. If an incident cycle <edge> is absent from the <tree>, its candidate is bounded by the cycle length. Otherwise its two neighbours lie in distinct <tree> branches, and some <edge> on the remaining cycle segment crosses branches. That <edge> is non-tree; shortest distances to its endpoints are bounded by the two complementary cycle segments, again giving a candidate no greater than the optimum. Thus the minimum candidate equals the shortest-cycle length. Repeated <Dijkstra algorithm> runs take $O((|V|^2+|V||E|)\log(|V|+1))$ <running time> with a <binary heap>.
Back to article page
