Given G = (V,E) directed graph, w: E->R weight function. Describe efficient algorithm to compute for every v in V if v is in a negative cycle (not necceserally simple)
My solution: (in O(EV^4) is it optimal?)
Build a new graph G', containing |V| layers, such that for every v in V :
v_i,j is vertice v_j in layer i.
draw an edge from vertice to another in the next layer if theres such an edge in the original graph.
if theres a shortest path fromv_i,j to v_k,j which is < 0 then this vertice belongs to a negative cycle.
we have |V| layers. we need to run BF for every v in V.
V' = (V^2) , E' = (EV)
so complexity is: V*(EV*V^2)=O(EV^4)
is there a solution with a better complexity?