[알고리즘] C로 구현한 다익스트라 최단경로..

주어진 알고리즘을 c로 구현한 것입니다.

어디까지나 구현에 목적을 두었으므로 최적화된 코드가 아님을 알려드립니다..

// 최단경로 Dijkstra Algorithm을 이용한 해법

#include <stdio.h>
#include <stdlib.h>

#define n 6 // 정점이 몇개인지를 정의
#define m 9999 // 연결되지 않은 정점끼리는 9999라는 값으로 끊어졌음을 표시..

int flag[n+1],dist[n+1]; // 거리 결정난곳 체크 배열과 거리 배열
int i,j,min,bk; // i,j는 for문 돌릴때 쓰는거 min은 최소값 갱신시 사용,bk는 위치 백업
int data[n+1][n+1] = {
 {0,0,0,0,0,0,0},
       {0,0,2,m,3,m,m},
       {0,m,0,4,1,m,m},
       {0,m,m,0,4,1,3},
       {0,m,2,2,0,1,m},
       {0,m,m,1,m,0,6},
       {0,m,m,m,m,m,0}};  // 기본적으론 파일로 입력 받아야 겠지만.. 예제이므로 이렇게 입력. 인접행렬방법으로 그래프를 배열에 입력...

void main()
{
  for (i=1;i<=n;i++) {  // 초기화 부분
     flag[i] = 0;
     dist[i] = 9999;
  }
  dist[1] = 0;  // 1번점부터 어떤점까지를 이 소스에선 구할꺼라서 1부터 0으로 초기화 하고 시작합니다.
  for (i=1;i<=n;i++) {
     min = 32767;  // 일단 무한대(걍 큰수)로 초기화 하고
     for (j=1;j<=n;j++) {
        if (min>dist[i] && flag[j]==0) {  //dist[i]의 값이 for j 돌리면서 구한 최소값보다 작으면 그리고 아직 결정나지 않은 정점이라면
           min = dist[i]+data[i][j];  // 갱신합니다
           bk = j;  // 현재 위치 백업
        }
     }
     flag[bk] = 1;  // 현재 위치(정점)은 최소값으로 결정되었으니 1로 막아놓음..
     for (j=1;j<=n;j++) {
        if (dist[j] > data[bk][j]+dist[bk] && data[bk][j] != m)
// 현재 위치에서의 j 위치로 가는데까지의 값보다 이때까지 구한 j까지의 거리가 더 크면  그리고 해당 부분이 끊어지지 않았다면
        {
           dist[j] = data[bk][j] + dist[bk];  // 거리 배열을 갱신합니다
        }
     }
  }

  for (i=1;i<=n;i++) {
   printf("1 ~ %d : %d\n",i,dist[i]); // 1부터 각각의 점까지의 거리의 최소 값을 출력
  }

}

본 자료는 다른곳에서 스크랩한 자료 입니다.

출처를 아신분은 댓글로 달아주세요