hi.

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)

complexity: O(V×E)

i would be thankful if someone helped me in knowing if this algorithm is right or wrong.