Enjoy an ad free experience by logging in. Not a member yet? Register.

Results 1 to 7 of 7
Thread: Dijkstras ALgorithm..

02242005, 04:22 PM #1
 Join Date
 Feb 2005
 Posts
 5
 Thanks
 0
 Thanked 0 Times in 0 Posts
Dijkstras ALgorithm..
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??
Thxs.

02242005, 04:52 PM #2
 Join Date
 Jun 2002
 Location
 Sydney, Australia
 Posts
 3,531
 Thanks
 0
 Thanked 1 Time in 1 Post
I'm not familiar with that algorithm. Perhaps you should look up A* path finding.
Omnis mico antequam dominus Spookster!

02242005, 09:02 PM #3
 Join Date
 Feb 2005
 Posts
 5
 Thanks
 0
 Thanked 0 Times in 0 Posts
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.

02242005, 09:12 PM #4
 Join Date
 Jun 2002
 Location
 Sydney, Australia
 Posts
 3,531
 Thanks
 0
 Thanked 1 Time in 1 Post
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.
Omnis mico antequam dominus Spookster!

02252005, 01:09 PM #5
 Join Date
 Feb 2005
 Posts
 5
 Thanks
 0
 Thanked 0 Times in 0 Posts
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.

03012005, 09:25 PM #6
 Join Date
 Feb 2005
 Posts
 5
 Thanks
 0
 Thanked 0 Times in 0 Posts
any ideas?
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

03312005, 02:56 AM #7
 Join Date
 Feb 2005
 Posts
 27
 Thanks
 0
 Thanked 0 Times in 0 Posts
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.