Heard of Dijkstra?

[summit]

Hi, I'm new to PHP and have some code which is buggy. I cant find the problem - maybe i'm being totally useless. More than likely. I am trying to find the shortest path from city to city.

 

Sample data may be

<DATA>

Aberystwyth:Birmingham:92:train

Aberystwyth:Gloucester:86:train

Barrow:Sunderland:91:train

Barrow:Blackpool:22:bus

Bournemouth:Winchester:33:train

Bournemouth:Stratford:98:train

Bournemouth:Cardiff:78:bus

 

And so far I have:

 

<?php

 

# Assumes: $origin and $dest are valid cities

$connection = mysql_connect(":/Applications/MAMP/tmp/mysql/mysql.sock", "******", "******") or die ('cannot reach database');

$db = mysql_select_db("cities") or die ("this is not a valid database");

 

$routes = mysql_query("SELECT from, to, weight, mode FROM journeys");

 

# Populate routes

# foreach (@lines){

# if (! $routes[$from]) $routes[$from] = array();

# $routes{$from][$to] = array( "weight" => $w,

# "method" => $m };

# }

 

$set = array(

"$origin" => array(

"best_weight" => 0,

"best_from" => '',

"visited" => array(),

)

);

 

$visited_nodes = 1;

while ($visited_nodes){

$visited_nodes = 0;

while (list($city, $v_data) = each($set)){

while (list($routes,$r_data) = each($routes[$city])){

if ($v_data["visited"][$route]);

$visited_nodes++;

$c_weight = $r_data["weight"] + $v_data["best_weight"];

if ($set[$route]){

if ($set[$route]["best_weight"] > $c_weight){

$set[$route]["best_from"] = $city;

$set[$route]["best_weight"] = $c_weight;

}

$set[$route]["visited"][$city] = 1;

}

elseif (!$set[$route]){

$set[$route] = array(

"visited" => array($city => 1),

"best_from" => $city,

"best_weight" => ($c_weight));

}

$v_data["visited"][$route] = 1;

}

}

}

$route = array($dest);

while ($route[0] != $origin){

array_unshift($route, $set[$route[0]]["best_from"]);

}

 

print "Best route:\n";

print ($route);

print "\n";

 

?>

 

[move]I'm going nuts.[/move]

[Jessica]

You didn't tell us what the problem is.

Please post code between code tags!