i need help in the following problem.
we have a weighted directed graph 'G' (negative weights and cycles are possible), and a source node 's'. for each node 'u' in 'G' we want to know the value 'd[u]' defined as follows:
d[u] is the maximal possible value such that: for any path from 's' to 'u' (let 'l' be its length). we have 'l' >= d[u].
in other words:
d[u] = +OO if such path doesn't exist.
d[u] = -OO if we can reach a negative cycle from 's', then reach 'u' from this negative cycle.
otherwise, we have d[u] = the shortest simple path from 's' to 'u'.
note that the path can repeat the same vertex. 'OO' stands for infinity.
i searched a lot and didn't find an answer. i read somewhere that this problem is still NP. however here is my proposed solution.
for each 'u' in G d[u] = +OO d[s] = 0 repeat V-1 times // bellman-ford for each edge (u, v) if(d[v] > d[u] + weight(u, v)) d[v] = d[u] + weight(u, v); repeat V times for each edge (u, v) if(d[v] > d[u] + weight(u, v)) d[v] = d[u] + weight(u, v); mark v; for each 'u' in G if 'u' is marked d[u] = -OO
assume that (OO + some value = OO)
i would be thankful if someone helped me in knowing if this algorithm is right or wrong.