Solved

Posted on 2004-10-23

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.

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.

8 Comments

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/

(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).

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.

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

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.

I appreciate all your help,

Roy.

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

By clicking you are agreeing to Experts Exchange's Terms of Use.

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.

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

Connect with top rated Experts

**11** Experts available now in Live!