Modification of the Dijkstra's algorithm when the edges of the graph are percentages

Question

If I have a Graph where the nodes are cities and the edges are the percentage of resources that I lose going from one city to another, why can't I use the Dijkstra's algorithm to find the path (from city A to city B) where I will lose the least amount of resources? I've been trying to find a counterexample but I wasn't able to. Could somebody please help me?

Answer 1

I assume the percentages remaining are multiplied. That is, if you lose $20$% going from A to B and $30$% going from B to C then you have $70$% of $80$% left so you have lost 44%. If there was an edge from A to C along which you lost $49$ percent, then Djikstra's algorithm would pick this path, but you'd only have $51$% of your resources left if you followed it.

Djikstra's algorithm works for additive weights, in graph's with no cycle of negative weight. Since you don't have additive weights, there is no reason to believe you can use Djikstra's algorthm. You can't apply a theorem unless the hypotheses are satisfied.

Answer 2

Looks to me like you can use Dijkstra's algorithm just fine, if you replace "minimum" by "maximum" in your priority queue and replace "add the edge weight" by "multiply with the edge factor".

When applying a standard algorithm, a small bit of work like this is often needed to apply the algorithm's assumption's to the situation you meet the problem in. This is not generally considered to make it a different algorithm.

---

Of course, if you want to use an existing implementation of shortest-path finding, no matter whether it works by Dijkstra or something else, you can't just reinterpret the operations, but must do your adaptation in a different way (e.g., by taking logarithms of the edge factors).