Dijkstra's Algorithm for Negative Weights

Question

Okay, first of all I know Dijkstra does not work for negative weights and we can use Bellman-ford instead of it. But in a problem I was given it states that all the edges have weights from 0 to 1 (0 and 1 are not included). And the cost of the path is actually the product.

So what I was thinking is just take the log. Now all the edges are negative. Now I know Dijkstra won't work for negative weights but in this case all the edges are negative so can't we do something so that Dijkstra would work.

I though of multiplying all the weights by -1 but then the shortest path becomes the longest path.

So is there anyway I can avoid the Bellman-Ford algorithm in this case.

The exact question is: "Suppose for some application, the cost of a path is equal to the product all the weights of the edges in the path. How would you use Dijkstra's algorithm in this case? All the weights of the edges are from 0 to 1 (0 and 1 are not inclusive)."

Answer 1

If all the weights on the graph are in the range (0, 1), then there will always be a cycle whose weight is less that 1, and thus you will be stuck in this cycle for ever (every pass on the cycle reduces the total weight of the shortest path). Probably you have misunderstood the problem, and you either want to find the longest path, or you are not allowed to visit the same vertex twice. Anyway, in the first case dijkstra'a algorithm is definitely applicable, even without the log modification. And I am pretty sure the second case cannot be solved with polynomial complexity.

Answer 2

If your graph has cycles, no shortest path algorithm will find an answer, because those cycles will always be "negative cycles", as Rontogiannis Aristofanis pointed out.

If your graph doesn't have cycles, you don't have to use Dijkstra at all.

If it is directed, it is a DAG and there are linear-time shortest path algorithms.

If it is undirected, it is a tree, and it's trivial to find shortest path in trees. And if your graph is directed, even without cycles, Dijkstra still won't work for the same reason it doesn't work for negative edge graph.

In all cases, Dijkstra is a terrible choice of algorithm for your problem.

Answer 3

So you want to use a function, let's say F, that you will apply to the weights of the original graph and then with Dijkstra's algorithm you'll find the shortest product path. Let's also consider the following graph that we start from node A and where 0 < x < y < 1:

In the above graph F(x) must be smaller than F(y) for Dijkstra's algorithm to output correctly the shortest paths from A.

Now, let's take a slightly different graph that we start again from node A:

Then how Dijkstra's algorithm will work?

Since F(x) < F(y) then we will select node B at the next step. Then we'll visit the remaining node C. Dijkstra's algorithm will output that the shortest path from A to B is A -> B and the shortest path from A to C is A -> C.

But the shortest path from A to B is A -> C -> B with cost x * y < x.

This means we can't find a weight transformation function and expect Dijkstra's algorithm to work in every case.

Answer 4

You wrote:

I though of multiplying all the weights by -1 but then the shortest path becomes the longest path.

To switch between the shortest and the longest path inverse the weights. So 1/3 will be 3, 5 will be 1/5 and so on.