Code of oliver
<?php set_time_limit(60); $time_start getmicrotime();
/********************************************************************************************
*                                                                                           *
*   AUTOR:   Oliver Heil (oheil@ecc-gmbh.de)                                                *
*                                                                                           *
*   FILE:    pizza_dude.php                                                                 *
*   CREATE:  2003/08/14                                                                     *
*                                                                                           *
********************************************************************************************/

// ARRAY's FOR LATER USE
$map $dest $routes = array();

// READ "map.txt" AND BUILD MAP MATRIX
$fmap fopen("map.txt""r");

    while (!
feof($fmap)) {

    
$item explode(" "strtoupper(chop(fgets($fmap))));

    
$map[$item[0]][$item[2]] = $item[1];

        if (
$item[3] == 2) {

        
$map[$item[2]][$item[0]] = $item[1];
        }
    }

fclose($fmap);

$sm count($map);

    
// KALKULATE MAP MATRIX (Floyd Algorithmus / Adjazenzmatrix)
    
for ($k=0$k $sm$k++) { $kc chr($k+65);

        for (
$i=0$i $sm$i++) { $ic chr($i+65);

            for (
$j=0$j $sm$j++) { $jc chr($j+65);

                if (
$i == $j$map[$ic][$jc] = "x";
                else {

                    if (empty(
$map[$ic][$jc])) $map[$ic][$jc] = 99999999999999999999// INFTY ...
                    
else $map[$ic][$jc] = min($map[$ic][$jc], $map[$ic][$kc] + $map[$kc][$jc]);
                }
            }
        }
    }

// READ "dest.txt" IN "destinations" ARRAY FOR DELIVERY
$fdest fopen("dest.txt""r"); $destinations explode(" "strtoupper(chop(fread($fdestfilesize("dest.txt"))))); fclose($fdest);

// BUILD DESTINATION MATRIX
$u=0;

    foreach(
$destinations as $i) { $v=0;

        foreach(
$destinations as $j) {

        
$dest[$u][$v++] = strval($map[$i][$j]);
        }

    
$mapping[$i] = $u++;
    }

$sd count($dest);

    
// LOOP ALL DESTINATION NODES AS BEGINNING NODE
    
foreach ($destinations as $begin) {

    
// INITIALIZE array $VISITED, int $SUM, string $ROUTE
    
$visited array_flip($destinations); $sum 0$route "";

    
// SET BEGINNING NODE AS AKTUELL AND UNSET IT IN VISITED ARRAY
    
unset($visited[($aktuell $begin)]);

        
// LOOP ALL VISITED NODES
        
do { $ways = array();

        
// APPEND AKTUELL NODE ON ROUTE
        
$route.= $aktuell." ";

            
// LOOP ALL NOT VISITED NODES
            
foreach ($visited as $visit_k=>$visit_v) {

            
// CALL "Branch_and_Bound" FUNKTION AND STORE RESULTS IN WAYS ARRAY
            
$ways[$aktuell.$visit_k] = Branch_and_Bound($dest$sd$mapping[$aktuell], $visit_v);
            }

        
// FIND SHORTEST NODE
        
$shortest substr(array_search(min($ways), $ways), -1);

        
// SUMMARIZE WAYS
        
$sum += $dest[$mapping[$aktuell]][$mapping[$shortest]];

        
// SET SHORTEST NODE AS AKTUELL AND UNSET IT IN VISITED ARRAY
        
unset($visited[$aktuell $shortest]);

        
// HAS BEEN ALL NOTES VISITED ?
        
} while (count($visited) > 0);

    
// FILL ROUTES ARRAY
    
$routes[$route.$aktuell] = $sum;
    }

// DEBUG
//print_r($routes);

// SHOW SHORTEST ROUTE(S)
echo "\nShortest Route(s):\n\n";

    foreach (
array_keys($routes, ($min=min($routes))) as $shortest_route) {

    echo 
$shortest_route." [".$min."]\n";
    }

// SHOW RUNTIME
echo "\nRuntime: ".(getmicrotime() - $time_start)."\n";

// FUNKTION BRANCH_AND_BOUND
function Branch_and_Bound($dest$sd$d1$d2) {

$dest[$d2][$d1] = "x";

    for (
$i=0$i $sd$i++) {

        for (
$j=0$j $sd$j++) {

            if ((
$i == $d1) && ($j != $d2) || ($i != $d1) && ($j == $d2)) $dest[$i][$j] = "x";

        
// DEST_T (DEST MATRIX TRANSPONIERT)
        
$dest_T[$j][$i] = $dest[$i][$j];
        }
    }

    
// SUMMARIZE MIN's FROM DEST MATRIX AND DEST_T MATRIX
    
for ($i=0$i $sd$i++) {

    
$dest_min += min($dest[$i]); $dest_T_min += min($dest_T[$i]);
    }

return 
min($dest_min$dest_T_min);
}

// GETMICROTIME()
function getmicrotime(){

list(
$usec$sec) = explode(" ",microtime());
return ((float)
$usec + (float)$sec);
}

// END  2003 Oliver Heil
?>


Back to results


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