Dijkstra's pain in the ass
Feb. 1st, 2008 02:57 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoySo for Theory of Algorithms homework, we were given the following problem:
"Let G=(V,E) be a directed graph where each edge e in E has capacity
c(e) > 0. The capacity of a path P is the minimum capacity over the
edges in P.
Let s be a node in the graph and assume there is at least one path
from s to each node in V. Design an efficient algorithm to find
a maximum capacity path from s to each node in V."
My solution: Dijkstra's algorithm, only instead of taking minima you take maxima, and instead of adding, you take minima, and the roles of 0 and ∞ are swapped. And yes, this works, I proved its correctness.
What annoyed me was that I couldn't think of any way to prove this just by using the fact that Dijkstra's Algorithm works, and instead mimicked the proof of Dijkstra all the way through.
I couldn't think of a way at the time, but I can't help but suspect I just saved myself a tiny bit of thinking at the cost of a ton of writing. Now I'm going to keep thinking about this...
-Harry
Addendum: Thinking about it a little, I think the key here may be that [0,∞] under (listing multiplication first) (+,min) and under (min,max) are both idempotent semirings with the property that a≤1 ∀a (in the semiring order). That they're totally ordered in this order may also be relevant, but I suspect not. I'll check this later.
Later addendum: Total ordering is definitely necessary. Also, I realized I didn't say it, but above I was assuming commutativity; I don't think it's necessary, though. (Still haven't gone through and actually checked all this, but it looks like it ought to work. Just as long as you keep your left and right multiplication straight.)
"Let G=(V,E) be a directed graph where each edge e in E has capacity
c(e) > 0. The capacity of a path P is the minimum capacity over the
edges in P.
Let s be a node in the graph and assume there is at least one path
from s to each node in V. Design an efficient algorithm to find
a maximum capacity path from s to each node in V."
My solution: Dijkstra's algorithm, only instead of taking minima you take maxima, and instead of adding, you take minima, and the roles of 0 and ∞ are swapped. And yes, this works, I proved its correctness.
What annoyed me was that I couldn't think of any way to prove this just by using the fact that Dijkstra's Algorithm works, and instead mimicked the proof of Dijkstra all the way through.
I couldn't think of a way at the time, but I can't help but suspect I just saved myself a tiny bit of thinking at the cost of a ton of writing. Now I'm going to keep thinking about this...
-Harry
Addendum: Thinking about it a little, I think the key here may be that [0,∞] under (listing multiplication first) (+,min) and under (min,max) are both idempotent semirings with the property that a≤1 ∀a (in the semiring order). That they're totally ordered in this order may also be relevant, but I suspect not. I'll check this later.
Later addendum: Total ordering is definitely necessary. Also, I realized I didn't say it, but above I was assuming commutativity; I don't think it's necessary, though. (Still haven't gone through and actually checked all this, but it looks like it ought to work. Just as long as you keep your left and right multiplication straight.)
