This is quite a well-researched AI problem...normally discussed in relation
to the travelling salesman problem. (the complexity of the search increasing
exponentially (I think) with the number of interconnected nodes), as most
strategy games need to address this problem. Probably the most commonly used
solution is the A* algorithm. If you are interested, have a look at the
pathfinding section at www.gameai.com - there you will find links to a
number of implementations; sadly none in php. I would port one of them, but
sadly don't have the time (sorry!).
On another note, can anyone tell me how to read command line parameters
passed to a script (I'm running 4.0.6 under NT)?
Cheers,
Dave Mariner.
[EMAIL PROTECTED]
www.medlab-group.com
----- Original Message -----
From: "Vahan Yerkanian" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Tuesday, June 19, 2001 7:44 AM
Subject: [PHP] 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?
> The most know algorithm for this is called Dijkstra's algoritm.
>
> Is there anyone with math skills enough to code this? This will be sure a
big
> asset for our PHP community as any site dealing with some
shippment/ticket/route
> problems will require such code.
>
> 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
>
