Question

The Bellman-Ford algorithm for the shortest path problem with negative edge weights will report that there exists a negative cycle if at least one edge can still be relaxed after performing nm times of relaxations. The algorithm, however, does not specify which cycle is a negative cycle. Design an algorithm to report one such cycle if it exists. You should make your algorithm runs as fast as possible.

Answer 1

- Iterate over the Bellman-Ford algorithm n-1 time while tracking the parent vertex and store in an array.

- Do another iteration and if no relaxation of the edges occurs in the nth iteration then print of return "There are no negative cycle".

- Else, store the vertex of the relaxed edge at the nth iteration with a variable name.

- Then iterate over the vertexes starting from the store vertex until a cycle is found then print it out as the cycle of negative weight.

Step-by-step explanation:

The Bellman-Ford algorithm can be used to detect a negative cycle in a graph. The program should iterate over the algorithm, in search of a relaxed edge. If any, the vertex of the specified edge is used as a starting point to get the target negative cycle.