Im_pickle_Riiiiiiiiick's blog

shortest path with negative cycles
By Im_pickle_Riiiiiiiiick, history, 7 years 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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

AFAIK, your algorithm is correct (not sure if it optimal) [UPD: it was my mistake; see comments below]

The known NP-problem looking like this one is " find shortest path among paths which do not repeat any edge and/or vertex (i.e., each vertex and each edge can be contained in path not more that one time) ". It's rather easy to prove, that polynomial algorithm of solving such problem leads to polynomial problem of determining does graph contain Hamiltonian cycle.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i know the NP version. i was surprised not to find a solution for this version on google and wanted make sure this solution is ok.
    thank you very much for your help.

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

This solution is incorrect. Consider a graph with four vertices:

1 -> 2, cost 1
1 -> 3, cost 100000000
3 -> 4 -> 3 is a negative cycle of cost -1
4 -> 2, cost 100000000

After the first bellman ford you will have the distance from 1 to 2 equal to 1, distance from 1 to 3 equal to 1000000000, and distance between 3 and 4 equal to some negative number.

After the second bellmanford you will relax the distances between 3 and 4, marking both. However, the distance from 1 to 2 will stay equal to 1, and so it won't be marked. However, clearly the shortest path from 1 to 2 is -OO.

However, your solution is close to correct one. Indeed, all you need to change is to add a BFS / DFS after the second bellman ford that finds all the vertices reachable from the marked vertices and mark them as well.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks for the test case.
    now if you don't mind, i have another question. is it necessary to repeat the second bellman-ford V times or is it enough to repeat it only once?

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    The solution is actually even closer to correct than that. Just change

    d[v] = d[u] + weight(u, v);

    in the second Bellman-Ford to

    d[v] = -OO

    and now you can guarantee that the negative cycle propagates.

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

(deleted)

→ Reply