4 ms·

An interesting use case is if you want to need to apply graph algorithms to a problem where edges multiply instead of adding. Just take the log of the multiplie

An interesting use case is if you want to need to apply graph algorithms to a problem where edges multiply instead of adding. Just take the log of the multiplier and now your multiplication problem is addition. For example, suppose you cannot exchange the US dollar for the Russian ruble. You have to go through some path such as USD -> EUR -> RUB. Of all possible paths, which one gives you the most favorable exchange? You can use Bellman-Ford to find out.

deleted 4y ago
[deleted]
thaumasiotes 4y ago
> For example, suppose you cannot exchange the US dollar for the Russian ruble. You have to go through some path such as USD -> EUR -> RUB. Of all possible paths, which one gives you the most favorable exchange? Why is it necessary to assume I can't exchange dollars directly for rubles? If that is possible, wouldn't I still want whatever path has the most favorable exchange rate?
- hammock 4y ago
  It’s not. That’s the problem he’s defining. It’s a real world problem
thaumasiotes 4y ago
> An interesting use case is if you want to need to apply graph algorithms to a problem where edges multiply instead of adding. Just take the log of the multiplier and now your multiplication problem is addition. I don't see what this has to add over just using the weights as they are. Dijkstra's algorithm tracks the distance from a source node to a target node. There's nothing about the algorithm that says that distance must be the sum of all the edge weights along a path; if it's the product, the algorithm will work without any changes.[1] The only requirement on the distance function is that you know how to calculate d(s,t) from the two values d(s, t') and d(t', t). [1] You'll still have problems [with Dijkstra's algorithm] if some weights are greater than 1 and some aren't, which is the exact analog of the problems that occur when distance is additive and some weights differ in sign. But that has no bearing on whether you can use multiplication directly or you need to convert it to addition.
- krackers 4y ago
  >There's nothing about the algorithm that says that distance must be the sum of all the edge weights along a path I think it relies on the assumption that d(a, c) >= d(a, b) + d(b, c). You could relax this of course, but then you're just back to bellman-ford algorithm. When your distance aggregation is instead multiplicative and you allow multipliers < 1, this no longer holds. Edit: I see your footnote already mentions this. I agree, the key point here isn't really whether things add or not, it's whether your aggregate distances are monotonically increasing or not. If they are, you can use dijkstra. If not, you have to use bellman ford or the fancier algorithms like the one in the arxiv.
  - thaumasiotes 4y ago
    You're right about the difference between Dijkstra and Bellman-Ford. But I thought the question was "why would you want negative edge weights?", and this doesn't seem like an answer to that.

deleted 4y ago

[deleted]

thaumasiotes 4y ago

> For example, suppose you cannot exchange the US dollar for the Russian ruble. You have to go through some path such as USD -> EUR -> RUB. Of all possible paths, which one gives you the most favorable exchange? Why is it necessary to assume I can't exchange dollars directly for rubles? If that is possible, wouldn't I still want whatever path has the most favorable exchange rate?

hammock 4y ago
It’s not. That’s the problem he’s defining. It’s a real world problem

thaumasiotes 4y ago

> An interesting use case is if you want to need to apply graph algorithms to a problem where edges multiply instead of adding. Just take the log of the multiplier and now your multiplication problem is addition. I don't see what this has to add over just using the weights as they are. Dijkstra's algorithm tracks the distance from a source node to a target node. There's nothing about the algorithm that says that distance must be the sum of all the edge weights along a path; if it's the product, the algorithm will work without any changes.[1] The only requirement on the distance function is that you know how to calculate d(s,t) from the two values d(s, t') and d(t', t). [1] You'll still have problems [with Dijkstra's algorithm] if some weights are greater than 1 and some aren't, which is the exact analog of the problems that occur when distance is additive and some weights differ in sign. But that has no bearing on whether you can use multiplication directly or you need to convert it to addition.

krackers 4y ago
>There's nothing about the algorithm that says that distance must be the sum of all the edge weights along a path I think it relies on the assumption that d(a, c) >= d(a, b) + d(b, c). You could relax this of course, but then you're just back to bellman-ford algorithm. When your distance aggregation is instead multiplicative and you allow multipliers < 1, this no longer holds. Edit: I see your footnote already mentions this. I agree, the key point here isn't really whether things add or not, it's whether your aggregate distances are monotonically increasing or not. If they are, you can use dijkstra. If not, you have to use bellman ford or the fancier algorithms like the one in the arxiv.
- thaumasiotes 4y ago
  You're right about the difference between Dijkstra and Bellman-Ford. But I thought the question was "why would you want negative edge weights?", and this doesn't seem like an answer to that.