플로이드 알고리즘 : 최단거리검색

** 플로이드 알고리즘 : 최단거리검색 **

<?php

$n=8;
$m=5000;
$a = array();

$a[] = array(0,2,$m,$m,$m,3,$m,$m);
$a[] = array(2,0,4,1,$m,$m,$m,$m);
$a[] = array($m,4,0,$m,$m,$m,3,$m);
$a[] = array($m,1,$m,0,3,$m,2,$m);
$a[] = array($m,$m,3,3,0,$m,$m,4);
$a[] = array(3,$m,$m,$m,$m,0,6,$m);
$a[] = array($m,$m,$m,2,$m,6,0,4);
$a[] = array($m,$m,$m,$m,4,$m,4,0);

for($k = 0; $k < $n; $k++){
    for($i = 0; $i < $n; $i++){
        for($j = 0; $j < $n; $j++){
            if ($a[$i][$j] > $a[$i][$k] + $a[$k][$j]) { $a[$i][$j] = $a[$i][$k] + $a[$k][$j]; }
        }
    }
}

for($i = 0; $i < $n; $i++){
    for($j = 0; $j < $n; $j++){
        print $i . "=>". $j ." : " . $a[$i][$j];
        print "<br />";
    }
}
?>
출처 : http://rhio.tistory.com/56