서식스토리

지하철 역간 최단 거리 검색 프로그램을 만들어 보려고 검색하다보니
유명한 알고리즘 중 다익스트라 알고리즘이라는 걸 알게 되었습니다.
소스는 델파이와 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];
?>

$start   = ($_GET['start']=='') ? 0 : $_GET['start'];

$scale = ($_GET['limitCnt']) ? $_GET['limitCnt'] : 20;
$page_scale = 20;
$page = floor($start / ($scale * $page_scale));

$tmp = mysql_fetch_row(mysql_query("SELECT COUNT(*) FROM member A , ".$zTb['mem']." B ".$opt, $connect));
$total = $tmp[0];

$sql = "SELECT * FROM member limit ".$start.",".$scale;
$rs = mysql_query($sql, $connect);
while($row = mysql_fetch_assoc($rs))
{
}

if($total > $scale){  // 검색 결과가 페이지당 출력수 보다 크면

 if($start+1 > $scale*$page_scale){
  $pre_start = $page * $page_scale * $scale - $scale;
  echo "<td><a href='".$_SERVER['PHP_SELF']."?p=".$_GET['p']."&start=".$pre_start.$optStr."' onfocus=this.blur() class=xyz><img src=ListSrc/005.gif width=14 height=11></a></td>";
 }

 echo "<td style='padding:3px 4px 0 4px;'>";

 for($vj=0; $vj < $page_scale ; $vj++){
  $ln = ($page * $page_scale + $vj)*$scale;
  $vk = $page * $page_scale + $vj + 1;
  if($ln<$total) {
   if($ln!=$start) {
    echo " <a href='".$_SERVER['PHP_SELF']."?p=".$_GET['p']."&start=".$ln.$optStr."' onfocus=this.blur() class=xyz> ".$vk." </a>";
   } else {
    echo " <span style='color:#990000;font-weight:bold;'> ".$vk." </span>";
   }
  }
 }

 echo "</td>";

 if($total > (($page+1)*$scale*$page_scale) ) {
  $n_start=($page+1)*$scale*$page_scale;
  echo "<td><a href='".$_SERVER['PHP_SELF']."?p=".$_GET['p']."&start=".$n_start.$optStr."' onfocus=this.blur() class=xyZ><img src=ListSrc/006.gif width=14 height=11></a></td>";
 }
}

function getMonthEnd($month)
{
 if(strlen($month) == 6){
  $tmp = substr($month,0,4) .'-'. substr($month,4,2) .'-01';
 }else{
  $tmp = $month .'-01';
 }

 $tmp = strtotime("+1 month",strtotime($tmp));
 return date("d",strtotime("-1 day",$tmp));
}

if(eregi("(MSIE 5.5|MSIE 6.0)", $HTTP_USER_AGENT)) {
    Header("Content-type:application/octet-stream");
    Header("Content-Length:".filesize($Path));
    Header("Content-Disposition:attachment;filename=".$user_file);
    Header("Content-Transfer-Encoding:binary");
    Header("Pragma:no-cache");
    Header("Expires:0");
} else {
    Header("Content-type:file/unknown");
    Header("Content-Length:".filesize($Path));
    Header("Content-Disposition:attachment; filename=".$user_file);
    Header("Content-Description:PHP3 Generated Data");
    Header("Pragma: no-cache");
    Header("Expires: 0");
}

if (is_file($Path)) {
    $fp = fopen($Path, "rb");
    if (!fpassthru($fp)) fclose($fp);
    clearstatcache();
} else {
    echo "해당 파일이나 경로가 존재하지 않습니다.";
}

$t = file("../회원명단.csv");
$cnt=0;

    for($i=0;$i< sizeof($t);$i++){
        $s = explode(",",$t[$i]);

        $name  = $s[0];
        $lic_num = $s[1];
        $office  = $s[2];
        $phone = $s[3];
        $hp = $s[4];
        $email = $s[5];


        $sql = "insert into member (lic_num,name,office,phone,hp,email) values
            ($lic_num,'$name','$office','$phone','$hp','$email')";
        mysql_query($sql);


        $cnt++;

    }

    echo $cnt .'건 처리';