Dijkstra's algorithm for negative weights

Question

Well, first of all, I know that Dijkstra does not work for negative weights, and we can use Bellman-ford instead. But in the task, I was told that all edges have a weight of 0 to 1 (0 and 1 are not included). And the cost of the journey is actually a product.

So I thought, just take a magazine. Now all the edges are negative. Now I know that Dijkstra will not work for negative weights, but in this case all the edges are negative, so we cannot do something to make Dijkstra work.

I, although I multiply all the weights by -1, but then the shortest path becomes the longest path.

So in any case, I can avoid the Bellman-Ford algorithm.

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

Answer 1

So, you want to use a function, say F , that you apply to the weights of the original graph, and then using the Dijkstra algorithm you will find the shortest path to the product. Consider also the following graph starting with node A and where 0 < x < y < 1 :

In the above graph, F(x) should be less than F(y) for Dijkstra's algorithm to correctly derive shortest paths from A

Now take a slightly different graph, which we will start again with node A :

Then how does Dijkstra's algorithm work?

Since F(x) < F(y) , we will choose node B in the next step. Then we look at the remaining node C Dijkstra's algorithm will deduce 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 the cost x * y < x .

This means that we cannot find the weight conversion function and expect that Dijkstra's algorithm will work in each case.

Answer 2

If all the weights on the graph are in the range (0, 1) , then there will always be a cycle whose weight is less than 1 , and thus you will be stuck in this cycle forever (each pass on the cycle reduces the total weight of the shortest path). You probably misunderstood the problem, and you either need to find the longest path, or you are not allowed to visit the same peak twice. In any case, in the first case, dijkstra's algorithm is definitely applicable even without modifying the log . And I am sure that the second case cannot be resolved with polynomial complexity.

Answer 3

You wrote:

I would like to multiply all weights by -1, but then the shortest path becomes the longest path.

Invert the weight to switch between the shortest and longest paths. So 1/3 will be 3 , 5 will be 1/5 , etc.

Answer 4

If your graph has loops, no shortest path algorithm will find the answer, because these loops will always be “negative loops,” as Rontogiannis Aristofanis pointed out.

If your schedule does not have cycles , you do not need to use Dijkstra at all .

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

If it is not oriented, it is a tree, and it is trivial to find the shortest path in the trees. And if your graph is directed, even without cycles, Dijkstra will still not work for the same reason that it does not work for a negative graph graph.

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