Im_pickle_Riiiiiiiiick's blog

By Im_pickle_Riiiiiiiiick, history, 23 months ago, In English,

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.

Read more »