"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
There are three kinds of actuaries: those who can count, and those who can't.
Piet Souris wrote:hi DJ,
long time no see! You seem to be very busy, but that is a good thing.
I had to read that assignment twice, but I think I got it. You are given N cities (vertices) and M lines of input indicating where a pilot can fly to and from (edges). So, it is an undirected Graph with N vertices and M edges. And the question is what the shortest path is between any two cities. Correct me if I'm wrong. Now, first thing what comes to mind is Dijkstra's algorithm: Dijkstra.
So, have a read and see if you agree with me!
There are three kinds of actuaries: those who can count, and those who can't.
Bjoke: A "Bully Joke". A Statement or action made with malicious intent - unless challenged. At which point it magically transforms into "I was just funnin'" or "What's the matter, can't take a joke?"
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
Bjoke: A "Bully Joke". A Statement or action made with malicious intent - unless challenged. At which point it magically transforms into "I was just funnin'" or "What's the matter, can't take a joke?"
D.J. Quavern wrote:I had a look at the minimal spanning tree: so this is the one we have, but how do you deal with them when there are no weights on the branches?
D.J. Quavern wrote: I also looked at Dijkstra algorithm: how can it find the most optimal route when it can't see the path n+2? I mean what if it choses the cheapest weight (2), but the next-one is extra salty (45)? Maybe it's not the point and it's a very stupid question though.
A key point is that with Dijkstra, at step n you aren't committing to any one solution yet - you are handling *all* possible solutions, of length n. Or of a particular maximum cost. Well, not really *all* of the solutions, because you are weeding out the ones that waste time getting to the edge of your graph. But you are keeping a set of all the best solutions that would reach the current edge of the search area. Without committing to any one point on the edge, yet.
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
D.J. Quavern wrote:Uh, NP-hard? Wiki has a funny definition : "the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP"
D.J. Quavern wrote:(and about Dijkstra... I am almost with you on that one. Just need to understand how it "stores" the possible solutions!)
"If you lie to the computer, it will get you."
Favorite Granny's Wisdom Pearl
Bjoke: A "Bully Joke". A Statement or action made with malicious intent - unless challenged. At which point it magically transforms into "I was just funnin'" or "What's the matter, can't take a joke?"