Code of stephan
<?
// read map.txt
// eliminate 2-way streets
// eliminate duplicates, take only shortest ways
$map = array();
$handle = fopen ("map.txt", "r");
while (!feof ($handle)) {
$buffer = trim(fgets($handle, 4096));
$dummy = explode(" ", $buffer);
if(!isset($map[$dummy[0]][$dummy[2]]) || $map[$dummy[0]][$dummy[2]]>$dummy[1]) {
$map[$dummy[0]][$dummy[2]] = $dummy[1];
}
if($dummy[3]==2) {
if(!isset($map[$dummy[2]][$dummy[0]]) || $map[$dummy[2]][$dummy[0]]>$dummy[1]) {
$map[$dummy[2]][$dummy[0]] = $dummy[1];
}
}
}
fclose ($handle);
// read dest.txt
$route = explode(" ", $buffer);
$handle = fopen ("dest.txt", "r");
$buffer = trim(fgets($handle, 4096));
fclose ($handle);
$route = explode(" ", $buffer);
// we only need the shortest distances for our route-points
foreach($route as $start) {
foreach($route as $stop) {
if($stop!=$start) {
$tmp = calcdist($start, $stop, $map);
if($tmp) $shortestroutes[$start][$stop] = $tmp;
}
}
}
$result = calcshortest($route, $shortestroutes);
print $result["way"]." ".$result["distance"];
// calculates the best route based on $route and $shortestroutes
function calcshortest($route, $shortestroutes, $act="", $distance=0, $shortest=false, $reached=array(), $depth=0) {
if(sizeof($reached)>=sizeof($route)) {
return array("distance"=>$distance, "way"=>implode(",",$reached));
}
foreach($route as $next) {
$myreached = $reached;
if(in_array($next, $myreached)) continue;
$myreached[] = $next;
if(!$act || $shortestroutes[$act][$next]) {
$tmp = calcshortest($route, $shortestroutes, $next, $distance+$shortestroutes[$act][$next], $shortest, $myreached, $depth+1);
if(!$shortest || $tmp["distance"]<$shortest["distance"]) {
$shortest = $tmp;
}
}
}
return $shortest;
}
// calculates the shortest distance between points $start and $stop, based on $map
function calcdist($start, $stop, $map, $act="", $distance=0, $shortest=0, $reached=array(), $depth=0) {
if(!$act) $act=$start;
$reached[] = $act;
if(is_array($map[$act])) foreach($map[$act] as $nextstop=>$nextdistance) {
if(in_array($nextstop, $reached)) continue;
if($nextstop==$stop) {
if(!$shortest || $shortest>$distance+$nextdistance) {
$shortest = $distance+$nextdistance;
}
continue;
}
$tmp = calcdist($start, $stop, $map, $nextstop, $distance+$nextdistance, $shortest, $reached, $depth+1);
if($tmp && (!$shortest || $shortest > $tmp)) {
$shortest = $tmp;
}
}
return $shortest;
}
?>
Back to results
|
|
