Calculate shortest cycle that contains node $s$

Let $$G(V,E,w)$$ be a graph with no negative weights.

Describe an algorithm that returns the shortest cycle containing a node $$v$$.

I came across this algorithm https://courses.engr.illinois.edu/cs374/sp2017/labs/solutions/lab10-sol.pdf

I can't convince myself it is true, because $$d(s,v)+w(s,v)$$ might not be independant.

By that I mean that perhaps $$w(s,v)$$ is contained in $$d(s,v)$$.

An algorithm I came up with is as follows:

Result arr=[]
For x in N(v):  // N is neighbours of v
remove(v,x) // remove the edge (v,x)
T=Dijkstra_tree(x,G)
if(v is in T):
Add d(v,x)+w(v,x) to Result Arr// add the weight of the tree+ the removed edge to arr
return Min(Result arr)


This algorithm has a running time of $$O(|V|)(|E|+|V|\log(|V|)$$.

Because $$v$$ might have $$|V|-1$$ neighbours, and then we run Dijkstra every time on them.

The algorithm they presented has a much better complexity but I just can't convince myself it indeed works, while my algorithm fixed that issue, but costs a lot of runtime.

• What's the question? Jun 30 at 17:56
• Why does the algorithm presented in the link work? And if it doesn't, does the fix I provided make it work? Jun 30 at 17:57
• Is your graph directed or undirected? The algorithm in the link works for directed graphs (and is correct) Jun 30 at 17:58
• I assumed the solution to both would be the same, but in this instance I was working on an undirected graph. Jun 30 at 18:05

To answer the question "why is the linked algorithm correct?", first of all notice that it works for directed graphs.

We want to show that the shortest cycle containing $$s$$ consists of a shortest path from $$s$$ to some vertex $$v$$ plus the edge $$(v,s)$$ such that $$d(s,v) + w(v,s)$$ is minimized.

Let $$C = \langle s=v_0, v_1, \dots, v_\ell, s\rangle$$ be a cycle. Clearly, the length of $$C$$ is at least $$d(s, v_\ell) + w(v_\ell, s)$$. On the other hand, all shortest paths $$\pi$$ from $$s$$ to a vertex $$v$$ such that $$(v,s)$$ exist imply the existence of a cycle of length $$d(s,v) + w(v,s)$$ (notice, in particular, that any simple path from $$s$$ contains no edges entering $$s$$, hence $$\pi$$ does not already contain $$(v,s)$$).

The linked algorithm almost works when the graph is undirected. The only problem is that the shortest path $$\pi$$ from $$s$$ to $$v$$ might be a single edge $$(s,v)$$, and hence the concatenation of $$\pi$$ with $$(v,s)$$ would not yield a cycle.

To avoid this problem you can consider only the vertices $$v$$ that have depth at least $$2$$ in the shortest-path tree rooted in $$s$$. This only misses some cycles of length $$3$$, namely those of the form $$\langle s, u, v, s \rangle$$ where both $$u$$ and $$v$$ are neighbors of $$s$$. Fortunately, we can discover all such cycles in $$O(|E|)$$ time by checking all edges $$(u,v) \in E$$.

In an undirected graph $$G$$, remove vertex $$v$$ and find the shortest path between all pairs of vertices in $$N(v)$$; i.e. Find $$d(a,b):=$$shortest path between $$a,b\in N(v)$$ in graph $$G'=G-\{v\}$$.

Result is $$min\{d(a,b)+w(a,v)+w(b,v)|a,b\in N(v)\}$$.

• This doesn't seem to work if $G$ itself is a cycle of length $> 3$. Jun 30 at 19:50
• If $G$ is a cycle $v,a,v_1,...,v_n,b,v$ then by removing the vertex $v$ we find the shortest path $a,v_1,...,v_n,b$ between vertices of $N(v)$ and addition of $w(a,v)$ and $w(b,v)$ produces the cycle. Jun 30 at 20:58
• Oh, you meant $N(v)$ as the neighborhood of $v$! I think you should add that to your answer. Jun 30 at 21:20