Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# 'Shortest Path First' type algorithm

Posted on 2004-10-23
Medium Priority
1,210 Views
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
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points

LVL 84

Expert Comment

ID: 12390991
0

LVL 1

Expert Comment

ID: 12394320
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

ID: 12394881
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

ID: 12395017
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

ID: 12395360
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
- 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

ID: 12403262
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?

Roy.
0

LVL 31

Expert Comment

ID: 12404549
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

rt_vin earned 405 total points
ID: 12458435
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

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question