Solved

Shortest Route finder between 2 cities.

Posted on 2001-06-14
20
645 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
  • 8
  • 6
  • 2
  • +3
20 Comments
 
LVL 40

Accepted Solution

by:
RQuadling earned 150 total points
Comment Utility
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:RQuadling
Comment Utility
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:RQuadling
Comment Utility
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
 
LVL 1

Author Comment

by:vahan
Comment Utility
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:RQuadling
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
Anyone can finish the code so it accepts source and destination and returns the path?
0
Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

 
LVL 40

Expert Comment

by:RQuadling
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
I'm looking for a working code.
0
 
LVL 1

Author Comment

by:vahan
Comment Utility
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
Comment Utility
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:RQuadling
Comment Utility
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
Comment Utility
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
Comment Utility
Thanks, points have been shared.
Points for katyan -> http://www.experts-exchange.com/jsp/qShow.jsp?qid=20316219
Moondancer - EE Moderator
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Introduction HTML checkboxes provide the perfect way for a web developer to receive client input when the client's options might be none, one or many.  But the PHP code for processing the checkboxes can be confusing at first.  What if a checkbox is…
Author Note: Since this E-E article was originally written, years ago, formal testing has come into common use in the world of PHP.  PHPUnit (http://en.wikipedia.org/wiki/PHPUnit) and similar technologies have enjoyed wide adoption, making it possib…
Learn how to match and substitute tagged data using PHP regular expressions. Demonstrated on Windows 7, but also applies to other operating systems. Demonstrated technique applies to PHP (all versions) and Firefox, but very similar techniques will w…
The viewer will learn how to dynamically set the form action using jQuery.

762 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