최단거리 알고리즘

#include <stdio.h>

#define n 8
#define m 5000

void main()
{
  int data[8][8] = {
  {0,2,m,m,m,3,m,m},
  {2,0,4,1,m,m,m,m},
  {m,4,0,m,3,m,m,m},
  {m,1,m,0,3,m,2,m},
  {m,m,3,3,0,m,m,4},
  {3,m,m,m,m,0,6,m},
  {m,m,m,2,m,6,0,4},
  {m,m,m,m,4,m,4,0}};

int i, j, k, s, e, min;
int v[8], distance[8];

// 그래프는 사전에 주어진 그래프를 사용한다. 지금은 예를들어 표기를 한 것임.
printf("\n                   <다익스트라(Dijkstra) 알고리즘>                  \n");
printf("\n 주어진 그래프에서 출발점과 도착점을 입력하면 최단거리를 알려줍니다.");
printf("\n +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++");
printf("\n +                                                                 +");
printf("\n +                         [3]-------3-------[5]                   +");
printf("\n +                          |                / (                   +");
printf("\n +                          |               /   (                  +");
printf("\n +                          4             3      4                 +");
printf("\n +                          |           /         (                +");
printf("\n +                          |          /           (               +");
printf("\n +           [1]-----2-----[2]---1---[4]            [8]            +");
printf("\n +            (                       (            /               +");
printf("\n +              (                       (         /                +");
printf("\n +                3                       2      4                 +");
printf("\n +                 (                       (    /                  +");
printf("\n +                  (                       (  /                   +");
printf("\n +                  [6]----------6-----------[7]                   +");
printf("\n +                                                                 +");
printf("\n +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n");
////////////////////////////////////////////////////////////////////////////////////


printf("\n 출발점을 입력하시오. : ");
scanf("%d", &s);
printf("\n 도착점을 입력하시오. : ");
scanf("%d", &e);

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

  distance[s-1] = 0;

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

  v[k] = 1;

  if(min==m) break;

  for(j=0; j<8; j++)
  {
  if(distance[j] > distance[k] + data[k][j])
     distance[j] = distance[k] + data[k][j];
  }
}
  printf("\n %d에서 출발하여, %d로 가는 최단 거리는 %d입니다.\n\n", s, e, distance[e-1]);
}






출처 : http://blog.naver.com/dioxin132?Redirect=Log&logNo=20054640