[알고리즘] 다익스트라

 

1. 자료구조
   1. 연결 리스트
   2. 이진 트리
   3. 스택
   4. 큐
   5. 해시
2. 정렬
   1. 버블 정렬
   2. 선택 정렬
   3. 삽입 정렬
   4. 퀵 정렬
   5. 힙 정렬
3. 알고리즘
   1. 재귀 함수
   2. 너비 우선탐색(BFS)
   3. 깊이 우선탐색(DFS)
   4. 다익스트라

---

 

다익스트라(Dijkstra)

 

 

 

다익스트라 알고리즘은 각 노드간 가장 짧은 경로를 찾는 알고리즘이다.

GPS에 사용되는 알고리즘이다.

 

 

Dijkstra()

 

---

 

소스코드

#define __main

#ifdef __main

#include <stdio.h>

#define INF 10000
#define MAX 128

int d[MAX] = { 0 };
int v[MAX] = { 0 };
int xy[MAX][MAX] = { 0 };

int Get_Index(int n) {
	int min = INF;
	int index = 0;

	for (int i = 0; i < n; i++) {
		if (d[i] < min && v[i] == 0) {
			min = d[i];
			index = i;
		}
	}
	return index;
}

void dijkstra(int n, int start) {
	int current = 0;

	for (int i = 0; i < n; i++) {
		d[i] = xy[start][i];
	}
	v[start] = 1;

	for (int i = 0; i < n - 2; i++) {
		current = Get_Index(n);
		v[current] = 1;

		for (int j = 0; j < n; j++) {
			if (v[j] == 0) {
				if (d[current] + xy[current][j] < d[j]) d[j] = d[current] + xy[current][j];
			}
		}
	}
}

int main() {
	int n, m, x, y, tmp, start;

	scanf("%d %d %d", &n, &m, &start);

	for (int i = 0; i < n; i++) {
		d[i] = INF;
		v[i] = 0;

		for (int j = 0; j < n; j++) if (i != j) xy[i][j] = INF;
	}

	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &x, &y, &tmp);

		xy[x][y] = xy[y][x] = tmp;
	}

	dijkstra(n, start);

	for (int i = 0; i < n; i++) {
		printf("%d ", d[i]);
	}

	return 0;
}

/*

Test Input Data

10 13 0
0 1 2
0 4 3
1 7 7
1 8 1
8 3 1
8 4 2
4 6 2
3 6 1
3 9 3
7 5 1
9 5 2
5 6 3
6 2 1
*/

#endif