Yeah I know, I'm googling and yahooing and etc for the last 3 days
but my math knowledge is still insufficient to write a PHP code for
this. Any kind soul who can stop my pain?
Vahan
Gary Huntress wrote:
>
> Here is the text of an email that I googled (eeek! its a verb!)
>
> The algorithm you need is called "single-source, shortest path", also
> known as "Dijkstra's algorithm". Here's one way to implement it, in
> pseudo-code.
>
> Shortest route on graph of locations in Inform
> ----------------------------------------------
>
> For each location, we keep two properties: V (the visited flag) and C
> (initial step). We are given the values SOURCE (i.e., parent(NPC))
> and DEST, the destination. N is a global variable. S and T are
> queues or stacks.
>
> 1. (Initialise) Let SOURCE.V = 1 and SOURCE.C = 0. Let N = 0 and S
> and T be empty. Push SOURCE onto S.
>
> 2. (Take one step) For each location I in S consider each possible
> location J which is reachable in one step from I and has J.V = 0
> (i.e., hasn't been visited yet). Let J.V = 1. If N = 0, let J.C =
> J; otherwise J.C = I.C. If J = DEST, go to step 4. Otherwise,
> push J onto T.
>
> 3. (Repeat) If T is non-empty, let S = T, T be empty, N = N + 1 and go
> back to step 2. Otherwise, go to step 4.
>
> 4. (Done) If DEST.V = 0, then destination cannot be reached.
> Otherwise DEST.C is the initial step on the shortest path from
> SOURCE to DEST. N is the distance from SOURCE to DEST.
>
> Regards,
> Gary "SuperID" Huntress
> =======================================================
> FreeSQL.org offering free database hosting to developers
> Visit http://www.freesql.org
>
> ----- Original Message -----
> From: "Vahan Yerkanian" <[EMAIL PROTECTED]>
> To: <[EMAIL PROTECTED]>
> Sent: Saturday, June 16, 2001 1:30 PM
> Subject: Shortest route between 2 cities
>
> > Greetings All!
> >
> > I'm looking for a 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 including the structure of tables used.
> >
> > CREATE TABLE Cities (
> > cityID int(4) unsigned NOT NULL auto_increment,
> > cityName varchar(20) NOT NULL,
> > PRIMARY KEY (cityID),
> > UNIQUE cityID (cityID, cityName)
> > );
> >
> > 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 ( '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');
---------------------------------------------------------------------
Before posting, please check:
http://www.mysql.com/manual.php (the manual)
http://lists.mysql.com/ (the list archive)
To request this thread, e-mail <[EMAIL PROTECTED]>
To unsubscribe, e-mail <[EMAIL PROTECTED]>
Trouble unsubscribing? Try: http://lists.mysql.com/php/unsubscribe.php
