0

I have Vertices V={s,u,v,x} as well as Edges E={(s,u),(s,x),(s,v),(u,v),(v,x),(x,u)) as well as the following Weights:

W(s, u) = 1
W(v, x) = W(x, u) = W(s, v)=2
W(u, v) = -3
W(s, x) = -1

Now I am executing Initialize(G,w,s) making s the starting point and initialize s.d = 0. I need the shortest path distances of u,v,x. Since they are all connected to s, I can just use the weight of W(s, u), W(s, v), W(s, x). But x.d would be -1. Is that even applicable ? Could I now use this distance to correctly execute Relax(s,x,w) and get a correct output?

Thanks in Advance

Meli497
  • 43
  • 6

1 Answers1

0

As Dijkstra's algorithm with negative weights says, as long as there are no negative cycles, Bellman-Ford will converge. If there is a negative cycle, it will detect that fact.

If there are negative cycles then there is no solution for it but to pair the cost of getting from A to B with the set of negative edges that were visited along the way so that you can trace them out and not revisit them again. This is theoretically correct but expensive both in memory and running time.

btilly
  • 43,296
  • 3
  • 59
  • 88