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.

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.

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.

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");

euston.add(new Link(morningtonCrescent, 50, Link.NORTHERN));

euston.add(new Link(camdenTown, 60, Link.NORTHERN));

euston.add(new Link(kingscrossStPacras, 55, Link.WATERLOOANDCITY));

euston.add(new Link(warrenStreet, 70, Link.NORTHERN));

euston.add(new Link(warrenStreet, 70, Link.WATERLOOANDCITY));

morningtonCrescent.add(new Link(euston, 44, Link.NORTHERN));

//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.