= Solution
All <edge> lengths are positive, so run the <Dijkstra algorithm> from every source $s$, retaining distances $d_s$ and a <shortest-path tree> of its reachable component. Each run takes $O((|V|+|E|)\log(|V|+1))$ with a <binary heap>. The following scans after each run use only $O(|E|)$ additional work.
For a <directed graph>, inspect every closing <edge> $(u,s)$ and consider $d_s(u)+w(u,s)$ when $u$ is reachable. The <tree> route from $s$ to $u$ followed by this <edge> is a closed walk. Every directed cycle supplies one such upper bound by choosing any of its <vertices> as $s$; the shortest route to its predecessor is no longer than the corresponding cycle segment. Positivity lets any repeated portion be removed, so the smallest candidate is \b[the shortest directed-cycle length].
For an <undirected graph>, do \i[not] combine an <edge> with the distance between its endpoints indiscriminately: that can count traversal of one bridge out and back as a false cycle. Instead inspect only <edges> $\{u,v\}$ absent from the current <shortest-path tree>, with both endpoints reachable, and consider
$$
d_s(u)+w(u,v)+d_s(v).
$$
The two <tree> routes and this non-tree <edge> contain a genuine cycle. If they share a prefix, its cost is counted twice, so that cycle is no longer than the candidate. Every candidate is consequently at least the global shortest-cycle length.
To prove equality is attained, take a shortest cycle $C$ and a source $s$ on it. If either cycle <edge> incident to $s$ is absent from the <tree>, its candidate uses a shortest route no longer than the rest of $C$, so it is at most the length of $C$. Otherwise both incident <edges> are in the <tree>, and their other endpoints lie in different branches below $s$. Along the remaining segment of $C$, some <edge> crosses between different branches. Such an <edge> is not a <tree> <edge>. The two distances to its endpoints are bounded by the two corresponding, disjoint segments of $C$ from $s$; their sum plus the crossing <edge> is at most the length of $C$. Thus some candidate is no greater than the optimum, completing the proof.
Return the smallest finite candidate, or report acyclicity if none exists. The total <running time> is \b[$O((|V|^2+|V||E|)\log(|V|+1))$], as required. The ordinary convention is a simple <graph>; if parallel <edges> are allowed, track actual <edge> identities when excluding <tree> <edges>, and treat a self-loop as its own cycle rather than discarding it. This is <shortest cycle by repeated shortest-path trees>.
Back to article page
