PDA

View Full Version : Dijkstras ALgorithm..

ashy
02-24-2005, 03:22 PM
Hello,

I am currently coding a route finding system of the london underground on a mobile phone for my uni project.
I've created the map using a vector of vectors but need a way of path finding through. I am working on a dijktra's algorithm but having much trouble.

Could anyone advise me on what to do or supply some code?? :thumbsup:

Thxs.

Mhtml
02-24-2005, 03:52 PM
I'm not familiar with that algorithm. Perhaps you should look up A* path finding.

ashy
02-24-2005, 08:02 PM
hey there.

I am aware of A* and was unable to use it for the reason that it does not take into account lines (underground tube lines). Dijkstra's searches through a graph of nodes and edges mimicing stations and lines so it appeared to be the best solution.

If however you could avise me on an A* algorithm that can be adapted in a way to suit the london underground network that would be most excellent.

Thanks.

Mhtml
02-24-2005, 08:12 PM
I see your point. Well I have lots of bookmarked resources on path finding (I've been making a 3d game & engine) so I'll have a search and see what I might be able to come up with. I'll look up Dijkstras algorithm first and see what it's on about, you might have already found the best solution.

ashy
02-25-2005, 12:09 PM
Ok thanks, any help would be much appreciated so cheers. I've browsed through google quite a bit so there is a lot of source code to examine so I'll keep going.

ashy
03-01-2005, 08:25 PM
just wondering if anyone has any code ideas for a shortest path algorithm for a data stucture such as the following in Java:

Station euston = new Station("Euston");
Station morningtonCrescent = new Station("Mornington Crescent");
Station camdenTown = new Station("Camden Town");
Station kingscrossStPacras = new Station("Kings Cross St Pancras");
Station warrenStreet = new Station("Warren Street");

//and any other neighbouring nodes

cheers guys.

ash

JWizard
03-31-2005, 01:56 AM
O.K. So you have nodes(stations) and vertices(links). Dijkstra's algorithm is, in fact, a good choice for a solution(any faster has proven to be impossible to date).
I'm not going to code it for you, but here's what you need to do:

Create two integer label attributes for each station. This shouldn't be hard, since it appears as though you've already written a class definiton for station. Create functionality to get and set these labels. (You'll see why later).
Create a priority queue. I assume since you've evidently programmed before, you're familiar with this. Download some code if you need to.

Then the algorithm is pretty simple:

Input: some vertex v to start from.
Output: all labels are the shortest path from the input vertex to the each vertex.

v.label = 0;
for every other vertex vi{
vi.label = Infinity;
}
Put all the vertices into the priority queue Q(based on their labels as keys)

until(Q is empty){
v = Q.removeMin(); //removes the smallest labelled vertex from the priority queue
for each vertex x adjacent to v{
if ((u.label + lenghtOfLink(u,x)) < x.label)){
z.label = u.label + lengthOfLink(u,x);
change the key of x in Q to x.label
}
}
}

That's it. When this algorithm terminates, the labels of all vertices are the shortest paths from v to that vertex. you can easily remember the shortest path as you go, if you want to.

This is a great algorithm that runs in O((n + m)logn), with n vertices and m edges.

I hope I was of assistance. I know the pseudo code might be a bit confusing, but take a good look at it. It's the solution you want, and a fast one.