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($handle4096));
    
$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($handle4096));
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


© Copyright 2003-2023 www.php-editors.com. The ultimate PHP Editor and PHP IDE site.