Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 7 of 7
  1. #1
    New to the CF scene
    Join Date
    Feb 2005
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

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

  • #2
    Senior Coder Mhtml's Avatar
    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!

  • #3
    New to the CF scene
    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.

  • #4
    Senior Coder Mhtml's Avatar
    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!

  • #5
    New to the CF scene
    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.

  • #6
    New to the CF scene
    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

  • #7
    New Coder
    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.


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •