BellmanFord with negative cycles

Question

I need to find the shortest path in an undirected graph where each edge has a [weight, capacity]. The capacity in this case would be the maximum number of times it is allowed to traverse the edge. Negative weights are allowed and negative cycles would be permitted. Lets say I have an egde [-3, 2] from a to b, then it is allowed to go from a to b and back to a resulting in a total distance of -6. After the second traversal this edge cannot be taken anymore. I need to print out all the nodes forming the shortest path between source and destination given the capacity constraints.

Finding the shortest path without negative cycles I would use Bellman-Ford. I am not sure how this would work with negative cycles though and I cannot find anything in the literature about this problem. Should I just not use Bellman ford and use a depth first search to brute force this problem?

Answer 1

The Bellman-Ford algorithm runs a check for improvements to the distances to each node V - 1 times where V is the number of nodes ( vertices ). Each check loops over every edge.

If one of these checks finds no improvement after looking at every edge, then it exits early because we know that not further improvement is possible ( and no negative cycles exists )

If after running V-1 checks, finding an improvement every time and then one more complete check is done and a further improvement is found then we know that there exists at least one negative cycle exists ( because we are going around and around generating an "improvement" each time ). Normally this would be a cause to generate an error.

However, in your case, you allow a number of repeats around a negative cycle. You will now have to find the negative cycle(s) using depth first search and work out how many go-arounds are allowed.