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');
> --
> Vahan Yerkanian
[EMAIL PROTECTED]
> Vice President, Design & Development Website @
http://www.abideweb.com/
> AbideWeb Technologies, LLC Phone +3741 238650 | Mobile +3749
416358
>
> ---------------------------------------------------------------------
> 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
>
---------------------------------------------------------------------
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
