0
$\begingroup$

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.

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

2 Answers 2

1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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)\}$.

$\endgroup$
3
  • $\begingroup$ This doesn't seem to work if $G$ itself is a cycle of length $> 3$. $\endgroup$
    – Nathaniel
    Jun 30 at 19:50
  • $\begingroup$ 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. $\endgroup$ Jun 30 at 20:58
  • $\begingroup$ Oh, you meant $N(v)$ as the neighborhood of $v$! I think you should add that to your answer. $\endgroup$
    – Nathaniel
    Jun 30 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.