다익스트라(Djikstra)

⊙ 학습 목표

코드스니펫

 

다익스트라 알고리즘

다익스트라 알고리즘은 길찾기 알고리즘의 기초이다. 조건적인 부분들도 그렇고 이후 개념을 확장해 A* 알고리즘으로 넘어갈 수 있다. 다익스트라 알고리즘은 한 지점에서 다른 지점으로 가는 경로를 찾는게 목적이다.

특징

1. 다익스트라 알고리즘은 음의 가중치가 없을 때 사용한다.
2. 시작 지점 1개의 대해서 판별하는 알고리즘이다.

 

---

 

구현 방법

일단 시작 지점이 1이고 도착 지점이 5라고 생각하고 알고리즘을 실행해보자.

 

1. 일단 시작 지점부터 각 지점까지의 거리를 저장할 배열을 초기화해준다.

1	2	3	4	5
INF	INF	INF	INF	INF

 

2. 시작 지점의 비용을 0으로 계산한다.(시작->시작)

1	2	3	4	5
0	INF	INF	INF	INF

 

3. 시작 지점과 연결된 지점을 방문한다.(1->2, 1->3)

1	2	3	4	5
0	3	2	INF	INF

 

4. 방문한 지점은 2, 3번이다. 이후 이 지점들과 연결된 지점들을 탐색한다.

1	2	3	4	5
0	3	2	5(2+3)	10(3+7)

4번 지점의 경우 1->3->4 이므로 비용이 2+3=5가 되며 5번 지점은 1->2->5로 3+7=10이 된다.

 

5. 마지막으로 4번 지점과 연결된 곳을 탐색하고 존재한다.

1	2	3	4	5
0	3	2	5	8(5+3)

여기서 기존의 5번 지점까지 가는데 비용은 10(1->2->5)이었지만 4번을 거쳐 가는 방식이 더 빨랐으므로 (1->3->4->5 경로가 비용이 8) 더 빠른 경로의 비용으로 업데이트 해준다.

 

코드

int distFromStart[MAX];
bool visit[MAX];

void Djikstra(int start){
	// 시작 노드와 연결된 모든 정점들의 거리를 비교해 업데이트
	for(int i = 1; i <= 정점의 수; i++)
		distFromStart[i] = edge[start][i];
	
	// 시작 노드 방문 처리
	visit[start] = true;

	for(정점의 수만큼 반복)
	{
		int 다음 정점 = (방문한 정점들 중 가장 빠른 정점 탐색하는 함수);
		여기서 다음 정점에 대한 distFromStart 배열 수정
	}
}

 

---

 

배운 내용 정리

• 내용