Problems of detecting negative cycles using Bellman-Ford algorithm

Revision en1, by oos1111, 2018-06-27 04:04:57

When we use Bellman-Ford to get single source shortest path, we usually initialize the distance of all vertices to be INF and then set dis[src] to be 0, and next we run the algorithm. But now I don't want to get any shortest path, instead I want to find a negative cycle in the graph if there exists any. Since I don't have any source vertex now, how should I initialize the distance of vertices at first?

I think we can do the same initialization when we try to find the single source shortest path, so we can pick any vertex as the source and then run the algorithm since Bellman-Ford will detect the negative cycle if there exists one. But this seems to be wrong.

Tags graph, shortest-path, bellman-ford, negative cycle

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English oos1111 2018-06-27 04:38:48 0 Tiny change: 'zation of disdisdis. Why is s' -> 'zation of `dis`. Why is s' (published)
en3 English oos1111 2018-06-27 04:37:39 9842
en2 English oos1111 2018-06-27 04:13:24 539
en1 English oos1111 2018-06-27 04:04:57 755 Initial revision (saved to drafts)