Solved

'Shortest Path First' type algorithm

Posted on 2004-10-23
1,199 Views
Last Modified: 2008-01-09
Hi,

I wanted to make a railway program in java that could find the shortest path from one station to another, where some stations are on many railway lines. If the stations and railway lines are stored in a database, and the user selects the start and end station could a algorithm such as Dijkstra's Shortest Path Algorithm solve the problem?? Does anyone know how i can implement this in java?

Your help is very much appreciated,

Roy.
0
Question by:re08149383
    8 Comments
     
    LVL 84

    Expert Comment

    by:ozo
    0
     
    LVL 1

    Expert Comment

    by:mces
    Yes.  Since the edges (rail lengths) are not negative, Dijkstra can be used to solve the problem.
    Implementing Dijkstra in Java is a matter of a few lines of code, but the problem is that you need to have all your database loaded in memory.

    You can find an implementation here: http://renaud.waldura.com/doc/java/dijkstra/
    0
     
    LVL 31

    Expert Comment

    by:moorhouselondon
    With railway lines you have to interchange between them, there are 'weights' that needs to be considered.  On the London Underground, if one were travelling from Cockfosters to Earls Court the algorithm might work out that you travel on the Piccadilly line to Finsbury Park, change on to the Victoria line, travel to Green Park, then get back onto the Piccadilly line to finish the journey on that line.  If you were to do this it would appear shorter (less stations), but the interchange at Green Park takes 4-5 minutes (Finsbury Park is across the platform), then you have the headway between the trains to consider (and how many suitcases you were carrying).  This may result in the shorter journey taking longer in reality.  The 4-5 minute interchange, the frequency of the train service and the mobility of the passenger needs to be built into the algorithm.

    (I wrote a program in 8080 Assembler many years ago that worked out journeys accurately, but I used a much more basic technique than Dijkstra. For basic you can use the word lazy if you like).
    0
     

    Author Comment

    by:re08149383
    moorhouselondon,

    That's the sort of thing i want, but for simplicity lets say it takes 2 mins between stations and 5 mins for an interchange, and to find the shortest time... if i were to have two table one with station data and one with line data i.e cetral, district etc... i would face a many-many problem on the database side, so is there any way i could get around this?... I'm really stuck, cos i know i need an associative table in-between to make two one-many relationships, but i don't know what it should contain?... does anyone have any sample code to get this to work?

    Thanks,

    Roy.
    0
     
    LVL 31

    Expert Comment

    by:moorhouselondon
    The lazy way to do this is to start off at the Destination station (or the start location).  You have a linked list of the next stations for all stations.  The list for Earls Court would look something like this:-

    Earls Court
    - West Brompton
    - Olympia
    - West Kensington
    - Barons Court
    - Gloucester Road
    - High St Ken

    This is a simplification because I haven't put any "line" information in there

    So you do this for all stations.

    Initialise all stations with -1 value (ie an invalid value)

    Having done this, you then simply start off with a stationdistancefromstart=0 at Earls Court.  You then iterate through all stations and you say

    if the station being considered has a value >=0 then the Next stns to that station will get the next value up (provided they haven't already got a non zero value in them that is less than the current value) you've mentioned 2 mins, so let's so the iteration is 2.

    So at the end of the first iteration Earls Court will contain value 0, all of the other stations mentioned earlier will contain value 2.

    and so it goes, the loop ends when the destination gets the current iteration value stored.

    This is a simplification of course.  The "interchange" problem is left as an exercise for the reader - however for a cut in the profits of this app you are selling....       ;-))

    Earls Court actually is an example of a difficult (challenging) situation you will come up against as there are parallel routes which diverge at each end.

    I believe the technique outlined is called a Relaxation technique. Apply heat to the edge of a piece of iron.  The contours of colour that appear across the metal indicate the temperature rise spreading across the metal, but eventually equilibrium is reached when the metal reaches a steady temperature across its surface.
    0
     

    Author Comment

    by:re08149383
    Thanks for your reply... i admit that i don't really understand it as i have only just started to learn about databases and i've been given this assignment to do for college :( ........so i'm not selling it :-) he he. I've been told that i'm looking too much into this and that the solution is not that hard... hmmm, doesn't feel like it. I have to put all this data into databases with SQL and stuff and emphasise less on java and JDBC (unfortunatly), as if this was just a java exercise, i hopefully could've done this without any help. Do you think this can be done with databases?

    I appreciate all your help,

    Roy.
    0
     
    LVL 31

    Expert Comment

    by:moorhouselondon
    I believe the EE rules have something to say about questions such as this - another reason for pointing you iin the direction of answers, rather than solving them.  

    If the college say you should use Dijkstra, then I think they will want you to use Dijkstra.  You need to find a web link that explains Dijkstra in non-mathematical jargon, together with a simple example. A couple of EE'ers suggested links earlier on and I led you on what turns out to be a wild goose chase.  

    In your situation Java is a bit like a car.  It sounds like if you wanted to get from London to Edinburgh, you are more interested in building the car that will take you there, rather than planning the journey itself. Agreed you will not get there without the car, but you can always hire one, or indeed you can fly there or go by train (i.e., you will find that you have more options as a systems analyst than as a programmer).

    0
     
    LVL 1

    Accepted Solution

    by:
    Are you allowed to redefine your specs?... i.e. if you are allowed to specify which lines to use then you can ensure you only have one or less interchange per journey... you can have a table that gives each station on a line a value and use that to determine the time... simply using if else statements in java for this for interchanges might help (hint hint hint).
    0

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone. Privacy Policy Terms of Use

    Featured Post

    What Security Threats Are You Missing?

    Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

    Suggested Solutions

    Title # Comments Views Activity
    code issue 8 56
    countClumps  challenge 10 52
    mergeTwo  challenge 13 42
    countPairs challenge 7 11
    A short article about a problem I had getting the GPS LocationListener working.
    This is about my first experience with programming Arduino.
    An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
    In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

    875 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    11 Experts available now in Live!

    Get 1:1 Help Now