Solved

Shortest Route finder between 2 cities.

Posted on 2001-06-14
20
655 Views
Last Modified: 2008-03-06
Greetings All!

I'm looking for a php code which will find the shortest route between 2 cities, with data
being stored in SQL tables listed below. Anyone has coded such a task ever? I'm ready
to give 300+ points to a working example.

CREATE TABLE Cities (
   cityID int(4) unsigned NOT NULL auto_increment,
   cityName varchar(20) NOT NULL,
   PRIMARY KEY (cityID),
   UNIQUE cityID (cityID, cityName)
);

# Dumping data for table 'Cities'
INSERT INTO Cities VALUES ( '1', 'A');
INSERT INTO Cities VALUES ( '2', 'B');
INSERT INTO Cities VALUES ( '3', 'C');
INSERT INTO Cities VALUES ( '4', 'D');
INSERT INTO Cities VALUES ( '5', 'E');
INSERT INTO Cities VALUES ( '6', 'F');
INSERT INTO Cities VALUES ( '7', 'G');
INSERT INTO Cities VALUES ( '8', 'H');
INSERT INTO Cities VALUES ( '9', 'I');

CREATE TABLE CityMatrix (
   matrixID int(4) unsigned NOT NULL auto_increment,
   SourceCityID int(4) unsigned DEFAULT '0' NOT NULL,
   DestinationCityID int(4) unsigned DEFAULT '0' NOT NULL,
   Distance int(5) unsigned DEFAULT '0' NOT NULL,
   Fare int(4) unsigned DEFAULT '0' NOT NULL,
   PRIMARY KEY (matrixID),
   UNIQUE matrixID (matrixID)
);

# Dumping data for table 'CityMatrix'
INSERT INTO CityMatrix VALUES ( '1', '1', '4', '5', '10');
INSERT INTO CityMatrix VALUES ( '2', '3', '4', '50', '5');
INSERT INTO CityMatrix VALUES ( '3', '4', '3', '60', '6');
INSERT INTO CityMatrix VALUES ( '4', '5', '7', '85', '8');
INSERT INTO CityMatrix VALUES ( '5', '1', '3', '70', '4');
INSERT INTO CityMatrix VALUES ( '6', '9', '6', '39', '6');
INSERT INTO CityMatrix VALUES ( '7', '8', '4', '10', '1');
0
Comment
Question by:Vahan Yerkanian
  • 8
  • 6
  • 2
  • +3
20 Comments
 
LVL 40

Accepted Solution

by:
Richard Quadling earned 150 total points
ID: 6191357
A nice little bit of recursion here I think. But this would be a BFI method. I suspect that there are a LOT better ways.

I notice from your data that it is longer and more expensive to go from 4 to 3 than it is to go from 3 to 4.

And you can't even get to 2! (Did you know that you can buy train tickets in England for train stations that don't exist! Cool!).

This is a sort of pseudo-code.

Might give you enough pointers to work with. I am sure someone will supply the complete answer though!


// Psuedo code.
// An index of source+destination may make speedier access?

$aRouteSteps[];
$aRouteDistances[];
$iCurrentDistance = 0;
$iShortestDistance = 99999;
$aShortestRouteSteps[];
$iSteps = 0;
$StartCityID = 0;
$EndCityID = 0;

select $StartCity,$EndCity in source+destination.
if found, then this SHOULD be the shortest route! If not, then the data is wrong!
if not found then you need to start at the $StartCity and follow all valid links out from the $StartCity.
As you jump from each city to city you store the distance and the route so far.
     You do NOT include cities that have already been used.
     You add the distance to the total distance.
When you get to the $EndCity, if the total distance is less than the shortest distance, then you store that info in the Shortest... fields.


This is like a tree recursion. Rather than walking a web (i.e. links to places we have already been), we simply ignore them if we have already visited them.
We also stop when we reach the end.

TreeWalk(CurrentLocation)
     {
     Is this location the EndCity?
          Yes
               Is the current distance less than the last total distance
                    Yes
                         Store the current information in the shortest... fields.
                         Exit this recursion.

     Loop through all destinations for this location
          Has destination already been visited on the route?
               No
                    Store the step and values;
                    Increment the step counter;
                    Call TreeWalk(Destination);
     }

0
 
LVL 40

Expert Comment

by:Richard Quadling
ID: 6191387
Ah!

As you exit the recursive loop, you need to be able to carry on from where you left off, so (I think), you need to pass the array with the location and make sure that it is passed by value, not by reference (i.e. you want the current values to move through the recursion in one direction only.

I think you should simply do ...

TreeWalk(CurrentLocation)
     {
     Is this location the EndCity?
          Yes
               Is the current distance less than the last total distance
                    Yes
                         Store the current information in the shortest... fields.
                         Exit this recursion.

     Loop through all destinations for this location
          Has destination already been visited on the route?
               No
                    Store the step and values;
                    Increment the step counter;
                    Call TreeWalk(Destination);
                    Remove the last step;
                    Decrement the step counter;
     }


0
 
LVL 40

Expert Comment

by:Richard Quadling
ID: 6191408
More!

If you get to a point where there are no locations to add, (i.e. you have visited ALL the cities and not arrived at the destination), you will need to trap that.

The recursion should test ALL routes, find the smallest that takes you from a to b. If the route is NOT determined, then there is no route available!
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 1

Author Comment

by:Vahan Yerkanian
ID: 6193899
Thanks for the basic idea.

Let me clarify database dump which I provided is just for example and i did it in hurry.
so, travel cost from A to B and vice versa is the same anyway, and all cities are interconnected someway. Now I remember there was a Dijkstra's algorythm for
finding the shortest route, do you remember the exact algo of it?
0
 
LVL 40

Expert Comment

by:Richard Quadling
ID: 6194404
If you understand this sort of thing ...

http://www-b2.is.tokushima-
u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml

Good luck!

I would really like to see a solution to this!

0
 
LVL 1

Author Comment

by:Vahan Yerkanian
ID: 6194585
I've found this page already myself, but am still unable to get my code working.
I'm keeping this question open, maybe someone else will help me.
0
 
LVL 1

Author Comment

by:Vahan Yerkanian
ID: 6199600
I've found this URL. If only someone good enough at math could
code this into PHP, our whole society will benefit for sure!

http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml
0
 
LVL 7

Expert Comment

by:KangaRoo
ID: 6199633
Hardly explainatory, I'm afraid. I wonder why they're all so find of animations with this thingy.

Did find a more usefull link burried in an old bookmark file: http://swww.ee.uwa.edu.au/~plsd210/ds/dijkstra.html

This is not something to be coded in an afternoon and if someone knows some PHP priority queue code - maybe some library functions I missed? - that would be helpfull.

I'd have to read up, Dijkstra's Algorithm is burried deep beyond the cobwebs of my memory.
0
 
LVL 1

Expert Comment

by:katyan
ID: 6199714
hi,
    here is a sample source code that follows dijkstra's algo to find shortest path :

------------
<?
$host = "localhost";
$user = "root";
$pass = "";
$dbname = "dijkstra";

$con = mysql_pconnect($host,$user,$pass);
if(!$con) {
      echo "Couln't connect to server !";
      die;
}

if(!mysql_select_db($dbname,$con)) {
      echo "Couldn't select database";
      die;
}

$query = "select cityID from Cities";
$qid = mysql_query($query);
if(!$qid) {
      echo "Unable to get City IDs";
      die;
}

$node = array();
$i = 1;

//selecting city IDs

while($row = mysql_fetch_array($qid)) {
      $node[$i][city_id] = $row[cityID];
      $node[$i][label] = 999999;
      $node[$i][done] = 'n';
      //echo $node[$i][city_id]."<br>";
      $i++;
}

$no_of_cities =  count($node);

//initializing distances from every city to others as 0

for($i=1;$i<=$no_of_cities;$i++) {
      for($j=1;$j<=$no_of_cities;$j++) {
            $node[$i][$j] = 0;
      }
}


//retriving source-destination pairs from database and putting them to array node.

$query = "select * from CityMatrix";
$qid = mysql_query($query);
if(!$qid) {
      echo "Unable to get City matrix";
      die;
}

while($row = mysql_fetch_array($qid)) {
      $node[$row[SourceCityID]][$row[DestinationCityID]] = $row[Distance];
      echo $row[distance];
}

//print_distance($no_of_cities,$node);

//taking source city for demo. use form to let user enter source city.
$source_city = 1;

echo "START<br>";
print_label($node);
dijkstra($node,$source_city);


function print_distance($no_of_cities,$node) {
      for($i=1;$i<=$no_of_cities;$i++) {
            for($j=1;$j<=$no_of_cities;$j++) {
                  echo "Source: $i   Destination: $j   Distance: ".$node[$i][$j]."<br>";
            }
      }
      echo "----------------------<br>";
      return;
}

function print_label($node) {
      $no_of_cities = count($node);
      for($i=1;$i<=$no_of_cities;$i++) {
            echo "City ID: ".$i."   Label: ".$node[$i][label]."   Done: ".$node[$i][done]."<br>";
      }
      echo "----------------------<br>";
      return;
}

function dijkstra(&$node,$source_city) {
      $STEP = 1;
      echo "STEP ".$STEP."<br>";
      $STEP++;
      $node[$source_city][label] = 0;
      update_neighbours($node,$source_city);
      $node[$source_city][done] = 'y';
      print_label($node);
      while(get_inf_node($node)) {
      echo "STEP ".$STEP."<br>";
      $STEP++;
      $min_node = get_min_node($node);
      update_neighbours($node,$min_node);
      $node[$min_node][done] = 'y';
      print_label($node);
      }
      
}

function update_neighbours(&$node,$city) {
      $no_of_cities = count($node);
      for($i=1;$i<=$no_of_cities;$i++) {
            if(($node[$city][$i] != 0) && ($node[$i][done] == 'n')) {
                  $node[$i][label] = $node[$city][label] + $node[$city][$i];
            }
      }
}

function get_min_node($node) {
      $min = 999999;
      $min_node;
      $no_of_cities = count($node);
      for($i=1;$i<=$no_of_cities;$i++) {
            if(($node[$i][label] < $min) && ($node[$i][done] == 'n')) {
                  $min = $node[$i][label];
                  $min_node = $i;
            }
      }
      return $min_node;
}

function get_inf_node($node) {
      $no_of_cities = count($node);
      for($i=1;$i<=$no_of_cities;$i++) {
            if($node[$i][done] == 'n') {
                  return true;
            }
      }      
      return false;
}

?>
-----------------------
i've used this site's data as example. populate ur database with the data used on this site(data from animation ).
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html

this should be output:
------------------
START
City ID: 1 Label: 999999 Done: n
City ID: 2 Label: 999999 Done: n
City ID: 3 Label: 999999 Done: n
City ID: 4 Label: 999999 Done: n
City ID: 5 Label: 999999 Done: n
City ID: 6 Label: 999999 Done: n
City ID: 7 Label: 999999 Done: n
City ID: 8 Label: 999999 Done: n
City ID: 9 Label: 999999 Done: n
City ID: 10 Label: 999999 Done: n
----------------------
STEP 1
City ID: 1 Label: 0 Done: y
City ID: 2 Label: 4 Done: n
City ID: 3 Label: 999999 Done: n
City ID: 4 Label: 85 Done: n
City ID: 5 Label: 999999 Done: n
City ID: 6 Label: 999999 Done: n
City ID: 7 Label: 999999 Done: n
City ID: 8 Label: 999999 Done: n
City ID: 9 Label: 999999 Done: n
City ID: 10 Label: 999999 Done: n
----------------------
STEP 2
City ID: 1 Label: 0 Done: y
City ID: 2 Label: 4 Done: y
City ID: 3 Label: 22 Done: n
City ID: 4 Label: 85 Done: n
City ID: 5 Label: 16 Done: n
City ID: 6 Label: 999999 Done: n
City ID: 7 Label: 999999 Done: n
City ID: 8 Label: 999999 Done: n
City ID: 9 Label: 999999 Done: n
City ID: 10 Label: 999999 Done: n
----------------------
STEP 3
City ID: 1 Label: 0 Done: y
City ID: 2 Label: 4 Done: y
City ID: 3 Label: 22 Done: n
City ID: 4 Label: 82 Done: n
City ID: 5 Label: 16 Done: y
City ID: 6 Label: 92 Done: n
City ID: 7 Label: 999999 Done: n
City ID: 8 Label: 49 Done: n
City ID: 9 Label: 999999 Done: n
City ID: 10 Label: 999999 Done: n
----------------------
STEP 4
City ID: 1 Label: 0 Done: y
City ID: 2 Label: 4 Done: y
City ID: 3 Label: 22 Done: y
City ID: 4 Label: 82 Done: n
City ID: 5 Label: 16 Done: y
City ID: 6 Label: 96 Done: n
City ID: 7 Label: 999999 Done: n
City ID: 8 Label: 49 Done: n
City ID: 9 Label: 999999 Done: n
City ID: 10 Label: 34 Done: n
----------------------
STEP 5
City ID: 1 Label: 0 Done: y
City ID: 2 Label: 4 Done: y
City ID: 3 Label: 22 Done: y
City ID: 4 Label: 82 Done: n
City ID: 5 Label: 16 Done: y
City ID: 6 Label: 42 Done: n
City ID: 7 Label: 999999 Done: n
City ID: 8 Label: 49 Done: n
City ID: 9 Label: 999999 Done: n
City ID: 10 Label: 34 Done: y
----------------------
STEP 6
City ID: 1 Label: 0 Done: y
City ID: 2 Label: 4 Done: y
City ID: 3 Label: 22 Done: y
City ID: 4 Label: 82 Done: n
City ID: 5 Label: 16 Done: y
City ID: 6 Label: 42 Done: y
City ID: 7 Label: 999999 Done: n
City ID: 8 Label: 49 Done: n
City ID: 9 Label: 53 Done: n
City ID: 10 Label: 34 Done: y
----------------------
STEP 7
City ID: 1 Label: 0 Done: y
City ID: 2 Label: 4 Done: y
City ID: 3 Label: 22 Done: y
City ID: 4 Label: 82 Done: n
City ID: 5 Label: 16 Done: y
City ID: 6 Label: 42 Done: y
City ID: 7 Label: 51 Done: n
City ID: 8 Label: 49 Done: y
City ID: 9 Label: 121 Done: n
City ID: 10 Label: 34 Done: y
----------------------
STEP 8
City ID: 1 Label: 0 Done: y
City ID: 2 Label: 4 Done: y
City ID: 3 Label: 22 Done: y
City ID: 4 Label: 63 Done: n
City ID: 5 Label: 16 Done: y
City ID: 6 Label: 42 Done: y
City ID: 7 Label: 51 Done: y
City ID: 8 Label: 49 Done: y
City ID: 9 Label: 121 Done: n
City ID: 10 Label: 34 Done: y
----------------------
STEP 9
City ID: 1 Label: 0 Done: y
City ID: 2 Label: 4 Done: y
City ID: 3 Label: 22 Done: y
City ID: 4 Label: 63 Done: y
City ID: 5 Label: 16 Done: y
City ID: 6 Label: 42 Done: y
City ID: 7 Label: 51 Done: y
City ID: 8 Label: 49 Done: y
City ID: 9 Label: 121 Done: n
City ID: 10 Label: 34 Done: y
----------------------
STEP 10
City ID: 1 Label: 0 Done: y
City ID: 2 Label: 4 Done: y
City ID: 3 Label: 22 Done: y
City ID: 4 Label: 63 Done: y
City ID: 5 Label: 16 Done: y
City ID: 6 Label: 42 Done: y
City ID: 7 Label: 51 Done: y
City ID: 8 Label: 49 Done: y
City ID: 9 Label: 121 Done: y
City ID: 10 Label: 34 Done: y
----------------------

here label is initially set to infinity (999999), then each step they are modified according to the algo. it has a bug, last city doesn't get updated properly. do it urself.

hope this help.

katy


0
 
LVL 1

Author Comment

by:Vahan Yerkanian
ID: 6199743
Anyone can finish the code so it accepts source and destination and returns the path?
0
 
LVL 40

Expert Comment

by:Richard Quadling
ID: 6201687
That's good!

I like it!

Does anyone have any sizeable data for this?

Maybe several thousand interconnected locations?
0
 
LVL 1

Author Comment

by:Vahan Yerkanian
ID: 6201919
RQuadling,

Can you finish the code and bring it to useful something for our community?

I'm ready to double the points for a working procedure which will be called like this

$route=shortest_route($source,$destination,$matrix);

where $source is the starting city, $destination is target city, and $matrix is the 2d array of city interconnections with distances between them

This function returns an array of CityIDs forming the route and the total distance:
something like this:

$route[Route]=array(1,4,7,9,4,3);
$route[Distance]=123;

This wil be really a useful function for us, PHP developers.
0
 
LVL 1

Author Comment

by:Vahan Yerkanian
ID: 6205049
I've found another algorithm, and it's source in C at

http://www.cs.panam.edu/~meng/Course/CS6345/Notes/chpt-5/node10.html

can anyone recode it into PHP taking into consideration the use of MySQL tables please?
0
 
LVL 1

Expert Comment

by:katyan
ID: 6205676
hi vahan,
    i thought that it was straight forward, to implement the functionality u asked for.
the basic code that implements the algo. (Dijkstra) is already there.. its a simple task to covert it into what u want.
0
 
LVL 1

Author Comment

by:Vahan Yerkanian
ID: 6205692
I'm looking for a working code.
0
 
LVL 1

Author Comment

by:Vahan Yerkanian
ID: 6209149
I found the solution by searching the PHP-general mailing list archives.
As no one proposed working solution, I'm deleting this question.
0
 
LVL 49

Expert Comment

by:DanRollins
ID: 7087284
Hi vahan,
You've requested to delete this question, but its status has remained as 'Pending Delete' because one or more comments have been added.  Normally, the only way to fully delete such a Question is to post a message to Community Support and ask for assistance.

EE is making a one-time database sweep to purge the Pending Delete Questions automatically.  During this sweep:

    vahan -- To allow the deletion to proceed:  Do nothing.
    EXPERTS -- Please DON'T POST a comment except to contest this deletion.

In the future, please refer to http://www.experts-exchange.com/jsp/cmtyHelpDesk.jsp#8 for instruction on deleting questions.

DanRollins -- EE database cleanup volunteer
0
 
LVL 40

Expert Comment

by:Richard Quadling
ID: 7088169
I think that a LOT of work was done on this and some points should be given.

I have a solution, but is based on the code of Katyan and the Dijkstra formula.

0
 
LVL 1

Expert Comment

by:Moondancer
ID: 7108428
Thank you.
I will return later this afternoon or tomorrow morning for Closing recommendation; does  point split sound right?
This will NOT be deleted.
Moondancer - EE Moderator
0
 
LVL 1

Expert Comment

by:Moondancer
ID: 7109406
Thanks, points have been shared.
Points for katyan -> http://www.experts-exchange.com/jsp/qShow.jsp?qid=20316219
Moondancer - EE Moderator
0

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Things That Drive Us Nuts Have you noticed the use of the reCaptcha feature at EE and other web sites?  It wants you to read and retype something that looks like this.Insanity!  It's not EE's fault - that's just the way reCaptcha works.  But it is …
This article discusses four methods for overlaying images in a container on a web page
Explain concepts important to validation of email addresses with regular expressions. Applies to most languages/tools that uses regular expressions. Consider email address RFCs: Look at HTML5 form input element (with type=email) regex pattern: T…
The viewer will learn how to dynamically set the form action using jQuery.

733 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