Girth of Undirected Graph with Positive Integer Weights

Question

Let $G = (V, E)$ be an undirected graph without self loops and with edge weights $w: E \to \mathbb{N}$. The girth $g(G)$ of $G$ is defined as the length of the shortest cycle in $G$, i.e.

$g(G) := \min\left\{ n \in \mathbb{N} \mid \exists \text{ cycle }(e_1, e_2, \dots, e_k) \text{ in $G$ satisfying } n = \sum_{i = 1}^k w(e_i) \right\}$.

GOAL. Determine $g(G)$ algorithmically and as efficient as possible in terms of time complexity. Note that it's not necessary to find corresponding cycle, length is sufficient.

I present my thoughts on this problem as following. If the graph is unweight, i.e. $w(v) = 1$ for all $v \in V$, we may start a breadth-first search traversal keeping track of the depth of each vertex. Once we detect an edge which leads to an already visited vertex $v$, a cycle is found. The length of the cycle is the difference of the current depth and the depth of $v$. BFS from each vertex and taking minimum should do the job, time complexity is $\mathcal{O}(|V| \times (|V| + |E|))$.

How to deal with edge weights? It seems natural to modify Dijkstra, but I do not see how, because the cycle with least edges may be different from the cycle of minimum weight, the shortest cycle. Is there still a way to use Dijkstra in order to solve this problem?

Can we adapt an all-pairs shortest path algorithm? I would appreciate a solution based on Floyd-Warshall, because of it's simplicity (if there is no faster algorithm). One may assume the graph to be dense, i.e. $|E| = \mathcal{O}(|V|^2)$, so the above solution is $\mathcal{O}(|V|^3)$.

Answer 1

You can use both algorithms to solve this problem (Dijkstra's and Floyd-Warshall's) and you do not need to adapt them: you can simply use their output.

As suggested in D.W.'s answer, you can compute the minumum $d(v,v)$ over all $v \in V$. Each value $d(v,v)$ represents the length of the shortest way to get from a vertex $v$ back to the same vertex $v$; that is, the shortest cycle through $v$. Therefore, the minimum $d(v,v)$ over all vertices represents the shortest cycle in the entire graph $G$.

To gain more intuition, note that the shortest cycle in $G$ will go through some vertices $\{v_1, v_2, ..., v_k\}$, and that $d(v_1,v_1) = d(v_2,v_2) = \: ... \: = d(v_k,v_k)$. You need to find the minimum $d(u, v)$ (where $u = v$) in the whole graph $G$. This information can be easily obtained by inspecting the diagonal of the output matrix of an all-pairs shortest-paths algorithm.

Observe that the above reasoning would not be valid if $G$ had negative edge weights, and you were looking for a simple cycle. This is because nothing prevents the algorithm from selecting the same edge twice.

Observe also that if the graph is a tree (i.e., it contains no cycles), then the girth can be considered to be infinity. This can be checked in a simple pre-processing step, using, for example, breadth-first search.

With respect to the running time, $|V|$ invocations to Dijkstra's algorithm will probably be faster - $O(|V|^2 \log |V|)$ - if the graph is sparse. If the graph is dense, Floyd-Warshall's algorithm is probably a better choice.

Answer 2

Use an all-pairs shortest-paths algorithm to find the distance from each vertex to each other vertex, call it $d(u,v)$. Now find the minimum value of $d(v,v)$ over all vertices $v$. That is the length of the shortest cycle.

Why does this work? Suppose the shortest cycle from $v$ to $v$ has length $\ell$. Obviously we will have $d(v,v) \le \ell$ (since we have a path from $v$ to $v$ of length $\ell$, the shortest such path is at most $\ell$). Conversely, we know there is a path of length $d(v,v)$ from $v$ to $v$; since it goes from $v$ to $v$, this is a cycle; so the length $\ell$ of the shortest cycle must satisfy $\ell \le d(v,v)$. We have proven both $d(v,v) \le \ell$ and $\ell \le d(v,v)$, so it follows that $\ell = d(v,v)$.