다익스트라

#include <stdio.h>
void main()
{
 int nNow, i, nMin, bVisit;
 int Wt[9][9] = {
  {0, 0, 0, 0, 0, 0, 0, 0, 0},
  {0, 0, 8, 3, 0, 0, 0, 0, 0},
  {0, 8, 0, 4, 5, 2, 0, 0, 0},
  {0, 3, 4, 0, 0, 0, 6, 0, 0},
  {0, 0, 5, 0, 0, 0, 0, 2, 0},
  {0, 0, 2, 0, 0, 0, 0, 0, 7},
  {0, 0, 0, 6, 0, 0, 0, 0, 3},
  {0, 0, 0, 0, 2, 0, 0, 0, 9},
  {0, 0, 0, 0, 0, 7, 3, 9, 0}
     };
 int DMin[9], DVi[9];
 int DMo[9];

 for( i=0; i<9; i++ )
 {
  DMin[i] = 999;
  DVi[i] = false;
 }

 // -- 시작 정점 설정
 nNow = 1;
 DMin[1] = 0;
 DVi[1] = true;

 while(1)
 {
  // -- 현재 정점과 인접한 정점을 찾음
  nMin = 0;
  bVisit = false;
  for( i=1; i<10; i++ )
  {
   if (Wt[nNow][i] != 0)
   {
    // -- 인접한 정점의 최소한의 가중치를 넣음
    if( DMin[i] > DMin[nNow] + Wt[nNow][i] )
    {
     DMin[i] = DMin[nNow] + Wt[nNow][i];
     DMo[i] = nNow;
    }

    if( DVi[i] == false )
    {
     bVisit = true;
     if( DMin[nMin] > DMin[i] )
      nMin = i;
    }
   }
  }

  // -- 인접한 정점이 없거나 방문할 정점이 없으면
  if( (nMin == 0) || (bVisit == false) || (nMin == 8) )
  {
   nMin = 0;
   // -- 방문하지 않은 정점 중에서
   // -- 최소 가중치의 값이 가장 작은 정점으로 이동
   for( i=1; i<10; i++ )
   {
    if( DVi[i] == false )
    {
     if( DMin[nMin] > DMin[i] )
      nMin = i;
    }
   }

   if( nMin == 0 )
    break;
  }
  nNow = nMin;
  DVi[nNow] = true;
 }

 i = 0;
 nNow = DMo[8];
 while( DMin[i] = nNow, nNow != 1)
 {
  nNow = DMo[nNow];
  i++;
 }
 for( nNow=i; nNow>=0; nNow--)
  printf("%d -> ", DMin[nNow]);
 printf("8 \n");
}