단일출발점 최단경로... Dijkstra Shortest Path

 이번에는 특이한 이름만큼이나 유명하신(?) Dijkstra께서 만드신 단일 출발점에서 최단 경로를 구하는 다익스트라 알고리즘이다. 플로이드의 알고리즘과의 차이라면 플로이드의 알고리즘이 각 정점에서 다른 모든 정점으로 가는 최단 경로를 모두 구했다면, 다익스트라 알고리즘은 하나의 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 구한다는 것이다.

 그러면 왜 플로이드 알고리즘과 세트로 포스팅 한 것이 아니고, 이렇게 떨어져서 포스팅 하게 되었냐고 한다면, 플로이드 알고리즘은 동적 계획법으로 만들어진 알고리즘이고, 다익스트라 알고리즘은 앞의 두 포스팅인 최소비용 신장 트리처럼 탐욕적인 방법으로 만들어진 알고리즘이기 때문이다.

 알고리즘의 전체적인 구조는 프림의 알고리즘과 거의 차이가 없으므로, 아래의 프림 알고리즘을 알고 있다면 이 알고리즘은 10~20분만에 해결 할 수 있다.
다익스트라 알고리즘에서 쓰일 텍스트 파일(dijkstra_array.txt)
5
 0  7  4  6  1
99  0 99 99 99
99  2  0  5 99
99  3 99  0 99
99 99 99  1  0

단일출발점 최단 경로 문제를 추는 다익스트라 알고리즘
#include <stdio.h>
#include <malloc.h>

typedef struct Edge // 이음선을 나타내는 구조체
{
int vertex[2]; // 시작점과 끝점
int cost; // 이음선의 가중치
}Edge;

int** make_array(int n); // 배열을 만드는 함수
void read_array(int* W[], int n); // 파일에서 배열값을 읽는 함수
void dijkstra(int n, int* W[], Edge F[]); // 다익스트라 알고리즘
// 변수 출력을 위한 함수
void print_value(int touch[], int length[], int n, int num);
FILE* file;

int main()
{
file = fopen("dijkstra_array.txt", "r");
if(file == NULL) {
perror("File open error");
return 0;
}

int n;
fscanf(file, "%d", &n);

int i;
int** W;
Edge* F = (Edge*)malloc(sizeof(Edge)*(n-1));

W = make_array(n); // W 배열 생성
read_array(W, n); // 파일에서 W 배열값 정보 읽기

// 다익스트라 알고리즘을 돌려서 나온 최단 경로를 F 이음선 집합에 저장
dijkstra(n, W, F);

// 단일 출발점 최단 경로 결과 출력
printf("\n## Dijkstra Shortest Path ##\n");
for(i = 0; i < n-1; i++)
printf("v%d-> v%d: %d\n", F[i].vertex[0]+1, F[i].vertex[1]+1, F[i].cost);

free(W);
free(F); 
fclose(file);

return 0;
}

int** make_array(int n) // N x N 배열 만들기
{
int i;
int** array;
n--;
array = (int**)malloc(sizeof(int*)*n);
for(i = 0; i <= n; i++)
array[i] = (int*)malloc(sizeof(int)*n);

return array;
}

void read_array(int *W[], int n) // 파일에게 배열값을 읽어 배열 G에 저장
{
int i, j;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
fscanf(file, "%d", &W[i][j]);
}

void dijkstra(int n, int* W[], Edge F[]) // 다익스트라 알고리즘
{
int i, vnear = 0;
int min, num = 0;
Edge e;
int* touch = (int*)malloc(sizeof(int)*(n-2));
int* length = (int*)malloc(sizeof(int)*(n-2));

for(i = 1; i < n; i++) {
touch[i] = 0; // 각 정점에 대해서, v1에서 출발하는
length[i] = W[0][i]; // 현재 최단경로의 마지막 정점을 v1
} // 으로 초기화한다.

// 그 경로의 길이는 v1에서의 이음선
// 상의 가중치로 초기화한다.

print_value(touch, length, n, num+1); // touch, length의 변화 값 출력
while( num < n-1) { // n-1개의 정점을 Y에 추가한다.
min = 99;
for(i = 1; i < n; i++) // 최단경로를 갖는지 각 정점을 점검
if( length[i] >= 0 && length[i] < min) {
min = length[i];
vnear = i;
}
e.vertex[0] = touch[vnear]; // e = touch[vnear]가 인덱스인
e.vertex[1] = vnear; // 정점에서 vnear가 인덱스인
e.cost = min; // 정점으로 가는 이음선
F[num] = e; // e를 F에 추가

for(i = 1; i < n; i++)
if(length[vnear] + W[vnear][i] < length[i]) {
length[i] = length[vnear] + W[vnear][i];
touch[i] = vnear; // Y에 속하지 않는 각 정점에 대해서,
} // 최단경로를 바꾼다.
length[vnear] = -1; // vnear가 인덱스인 정점을 Y에 추가
print_value(touch, length, n, num+2); // touch, length의 변화 값 출력
num++; // repeat(n-1 times)를 위한 변수
}
}

void print_value(int touch[], int length[], int n, int num) // 중간과정 출력
{
int i;
printf("%dth touch\t\tlength\n", num);
for(i = 1; i < n; i++)
printf("%3d", i+1);
printf("\t");
for(i = 1; i < n; i++)
printf("%3d", i+1);
printf("\n");
for(i = 1; i < n; i++)
printf("%3d", touch[i]+1);
printf("\t");
for(i = 1; i < n; i++)
printf("%3d", length[i]);
printf("\n");
}
결과는 다음과 같다.
이번 알고리즘 소스는 정말 프림 알고리즘의 소스와 크게 다를 것이 없다.
    참고자료
  • 알고리즘(Foundatations of Algorithms Using C++ Pseudocode) - Neapolitan, Naimipour 저 / 도경구 역

by sakuragi | 2007/05/09 03:01 | :: R space :: 과제 | 트랙백 | 덧글(7)

트랙백 주소 : http://sakuragis.egloos.com/tb/3388539
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Commented by 환상경 at 2007/05/09 22:06
후 알수 없는 알고리즘의 세계 =_=
Commented by lowid at 2007/05/10 12:28
자료구조랑 알고리즘이나 꽤나 겹치나 봅니다..
저거 자료구조시간때 배웠는데... 사실 저것도 전에 숙제였는데 못해갔다는 (몰랐으니까요)
사실 저렇게 생각하기 싫어서.. 암튼 다익스트라 싫어... 최단거리도 싫어 (.........)
Commented by sakuragi at 2007/05/11 11:23
환상경, 왜 이러세요. 환상경님도 알고리즘 배우시면서~~ :D
lowid, 네. 자료구조에서 배웠던 것의 효율을 따지는 것이 알고리즘이라는 느낌이더라구요. :)
저도 작년에 무쟈게 싫어했다는... = _=);;
Commented by LinDol at 2007/05/16 18:32
어렵다...ㅜ_ㅜ

알고리즘 알려줘요 사쿠락이옹~
Commented by sakuragi at 2007/05/17 02:52
LinDol, 어려워요. 저도 요즘 다른 건 거의 손도 못 대고 이것만 파는 중이예요. T_T
Commented by 에이쥬어 at 2007/08/09 22:51
그렇지만 이게 또 묘한 게, 다익스트라 알고리즘은 어떤 면에서는 동적 계획법이라고도 할 수 있으니..
Commented by sakuragi at 2007/08/14 12:38
에이쥬어, 알고리즘을 좀 더 이해하기 쉽게 하기 위한 분류법일 뿐이니까요. :)

:         :

:

비공개 덧글

◀ 이전 페이지          다음 페이지 ▶

:+: sakuragi's Steam :+: