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.