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!
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.
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!)