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

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

지하철 역간 최단 거리 검색 프로그램을 만들어 보려고 검색하다보니
유명한 알고리즘 중 다익스트라 알고리즘이라는 걸 알게 되었습니다.
소스는 델파이와 C로 된거 밖에 없어서, 해당 소스를 PHP 버전으로 바꿔봤습니다.
참고하세요.

<?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];



?>

출처 : http://rhio.tistory.com/57