Problems of detecting negative cycles using Bellman-Ford algorithm

Правка en1, от 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.

Теги 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)