Thread: Short

I am presently designing a simulator to find the shortest route between 2 noded say A and B. I have finished the interface and input interfacr from the user and i am using linked list... I am able to arrive at an array.. eg:-

Code:

          A          B          C          D         E        

A       0           2          -          1          2        

B       2           0          1          -          1

C       -            1          0          4         5

D       1            -          4          0         2

E       2            1          5          2        0

now this matrix represents all the nodes and the distance between them... "-" eans that there is no direct route between the two.. Now i want to find the shortest route beween 2 nodes.. say for example between A to C. So any algorithm or help woul be appreciated....

The network for the above matrix may look like this..

Code:

                           A -'------2--------B
                           |      '2        1 '   |
                           1       '   E  '       1
                           |      2'        '5    |
                           D--'------4----'---C

So the shortest route for the above is A to B to C that is 2 + 1 =3
The above example and matrix for that was a simple one.. But i have to do this for say 1000 noes sometimes... with all possible routes.. with all kinds of distance....

So any help,algorithms,links,code snipets etc etc would be appreciated..


Thanx in Advance

Search for "Dijkstra shortest paths".

http://ciips.ee.uwa.edu.au/~morris/Y.../dijkstra.html
http://renaud.waldura.com/doc/java/dijkstra.shtml

Also searching with relation to "graph theory" may help.

http://www.cs.byu.edu/courses/cs236/...7/Graphs7.html
http://www.cs.wpi.edu/~dobrush/cs504...ishi_cs504.htm