Shortest Path on a weighted graph with negative cycles

user_14920690 0
Viewed 55

I have a list of cities and an energy expenditure between each of them. I want to find the "best" (shortest) path between some specific pairs, that leads to the least energy loss. All roads are two-way roads, same energy expenditure from one city to another in a pair, but in the "best" path, each city should be visited only once to prevent looping around the same city.

I've tried making a directed adjacency list graph and using Bellman Ford but i am indeed detecting negative cycles, making the shortest path non-existent, but can't figure out how to make the algorithm go through each node only once to prevent looping. I've thought about using something like BFS to just print all the possible paths from a source node to a destination and somehow skip going through the same node (summing up the weights afterwards perhaps). Any ideas of how I would possibly solve this, either modding the Bellman Ford or the BFS or using something else?

shortest-path breadth-first-search graph-theory c algorithm
2 Answers

The problem of finding the lowest-cost simple path (a path that doesn’t repeat nodes) in a graph containing negative cycles is NP-hard, which means that at present we don’t have any efficient algorithms for the problem and it’s possible that none exists. (You can prove NP-hardness by a reduction from the Hamiltonian path problem: if you assign each edge in a graph cost -1, then there’s a Hamiltonian path from a node u to a node v if and only if the lowest-cost simple path between them has length n-1, where n is the number of nodes in the graph.)

There are some techniques to find short paths using at most a fixed number of hops. Check out the “Color Coding” algorithm for an example of one of these.

user_5015570
  1. add the absolute value of the most negative weight to EVERY weight.
  2. Apply the Dijkstra algorithm. https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
  3. Subtract absolute value of the most negative weight times number of hops from cost of optimal path found in 2
user_165820
Related