Problems of detecting negative cycles using Bellman-Ford algorithm

Правка en2, от oos1111, 2018-06-27 04:13:24

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 v as the source, namely setting dis[v] to be 0 and setting distance of all other vertices to be INF, and then run the algorithm. But this seems to be wrong. And the correct initialization seems to be setting distance of all vertices to be 0.

This confused me a lot. So I have two question: 1. How should I initialize the distance of vertices when I want to find a negative cycle in a graph? 2. Is it wrong if I pick any vertex as source and run Bellman-Ford when I try to find a negative cycle? And Why if this is wroong?

And here is the case where the above two choices of initialization give us the difference:

Теги graph, shortest-path, bellman-ford, negative cycle

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский oos1111 2018-06-27 04:38:48 0 Tiny change: 'zation of disdisdis. Why is s' -> 'zation of `dis`. Why is s' (published)
en3 Английский oos1111 2018-06-27 04:37:39 9842
en2 Английский oos1111 2018-06-27 04:13:24 539
en1 Английский oos1111 2018-06-27 04:04:57 755 Initial revision (saved to drafts)