다익스트라 알고리즘 - 최단거리 검색

지하철 역간 최단 거리 검색 프로그램을 만들어 보려고 검색하다보니
유명한 알고리즘 중 다익스트라 알고리즘이라는 걸 알게 되었습니다.
소스는 델파이와 C로 된거 밖에 없어서, 해당 소스를 PHP 버전으로 바꿔봤습니다.
참고하세요. 이 알고리즘을 이용하여 최단경로 검색프로그램을 직접 만들어봤습니다.
아주 정확히 계산을 해주더군요. ^^
(본 글은 제가 phpschool 팁텍에 올렸던걸 티스토리 개설해서 이곳에 옮긴 자료입니다.)

<?php



$n=8;

$m=5000;

$data = array();



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

$distance = array();
$v = array();

$s = 0; // 시작점
$e = 7; // 끝점

for($j=0; $j < $n; $j++)
{
$v[$j] = 0;
$distance[$j] = $m;
}

$distance[$s] = 0;

for($i=0; $i< $n; $i++)
{
$min = $m;
for($j=0; $j < $n; $j++)
{
if(($v[$j] == 0) && ($distance[$j] < $min))
{
$k = $j;
$min = $distance[$j];
}
}

$v[$k] = 1;
if($min == $m)
{
print '연결되어 있지 않습니다.';
exit;
}

for($j = 0 ; $j < $n; $j++)
{
if($distance[$k]+$data[$k][$j] < $distance[$j])
{
$distance[$j] = $distance[$k] + $data[$k][$j];
}
}

}

print $s." = ".$e." : ".$distance[$e];
?>