Dijkstra Alogithm

그래프로 이루어진 맵에서 Point to Point간의 최단경로를 찾는데 사용되는 알고리즘 중 하나이다.

 

각 노드간의 가중치가 존재하는 그래프에서 사용된다.

먼저, F, G, H 개념을 이해해야 한다.

 

F는 결과값으로, G + H를 의미한다.

G는 Start-> Now까지의 가중치 이다.

H는 Now-> End까지의 가중치 이다.

 

Node는Index, F, G, H, State, From 값을 가진다고 가정한다.

Index는 Node의 번호를 의미한다. 1번node, 2번node 등을 이야기 한다.

State는 Open, Close의 상태 두가지를 가진다.

From은 전 Node의 Index값을 가진다.

 

Node는 생성시 항상 Open으로 둔다.

 

순서

1. 출발 노드 선택
   • 출발노드를 선택하고, 선택노드까지의 G를 0으로 설정하고, 다른 모든 노드까지의 F를 무한대로 초기화 한다.
2. 현재 노드와 인접 노드 간의 가중치 계산
   • 현재 선택한 노드로부터 이웃된 노드까지의 거리를 전부 계산(가중치 확인) 을 하고, 인접한 노드의 G를 전부 갱신해준 다음, 현재 노드에서 이어졌다 라는 것을 인접노드의 From에 표기해준다.
   • 단, 이웃된 노드는 Close상태가 아니어야 한다.
   • 이웃된 노드의 F를 갱신해준다.
3. 현재 노드를 Close상태로 바꾸어준다.
4. 모든 노드를 확인하여, F값이 가장 작고, Close가 아닌 상태의 node를 선택하여 위의 순서를 반복한다.

 

예시.

위의 방식을 계속 반복해봐서 다음 이미지의 최단거리를 계산해보자.

우리는 ㄷ->ㅈ 까지의 최단거리를 계산할 것 이다.

 

Start

Index	ㄷ	ㄱ	ㅁ	ㅎ	ㅇ	ㄴ	ㅅ	ㅈ
From	-1	null	null	null	null	null	null	null
F	0	MAX	MAX	MAX	MAX	MAX	MAX	MAX
State	Close	Open	Open	Open	Open	Open	Open	Open

(ㄷ에서 시작함으로 ㄷ을 초기화 한다)

 

1.번째 반복

Index	ㄷ	ㄱ	ㅁ	ㅎ	ㅇ	ㄴ	ㅅ	ㅈ
From	-1	ㄷ	ㄷ	ㄷ	null	null	null	null
F	0	10	15	20	MAX	MAX	MAX	MAX
State	Close	Open	Open	Open	Open	Open	Open	Open

(ㄷ의 인접노드를 전부 계산하고 ㄷ를 Close해준다)

2. 번째 반복

Index	ㄷ	ㄱ	ㅁ	ㅎ	ㅇ	ㄴ	ㅅ	ㅈ
From	-1	ㄷ	ㄷ	ㄷ	ㄱ	null	null	null
F	0	10	15	20	30	MAX	MAX	MAX
State	Close	Close	Open	Open	Open	Open	Open	Open

(ㅁ은 ㄱ에서 이동해도 값이 같음으로, 이동하지 않는다.)

 

3. 번째 반복

Index	ㄷ	ㄱ	ㅁ	ㅎ	ㅇ	ㄴ	ㅅ	ㅈ
From	-1	ㄷ	ㄷ	ㄷ	ㅁ	ㅁ	null	null
F	0	10	15	20	20	25	MAX	MAX
State	Close	Close	Close	Open	Open	Open	Open	Open

(ㅁ이 그다음으로 작음으로, 계산. ㅇ을 ㅁ으로 계산했을 때, 더 작게 나옴으로 From, F갱신)

 

4. 번째 반복

Index	ㄷ	ㄱ	ㅁ	ㅎ	ㅇ	ㄴ	ㅅ	ㅈ
From	-1	ㄷ	ㄷ	ㄷ	ㅁ	ㅁ	null	ㅎ
F	0	10	15	20	20	25	MAX	40
State	Close	Close	Close	Close	Open	Open	Open	Open

(ㅎ 과 연결된 것은 ㅈ밖에 없음으로, ㅈ를 연결한다.)

 

5. 번째 반복

Index	ㄷ	ㄱ	ㅁ	ㅎ	ㅇ	ㄴ	ㅅ	ㅈ
From	-1	ㄷ	ㄷ	ㄷ	ㅁ	ㅁ	null	ㅇ
F	0	10	15	20	20	25	MAX	35
State	Close	Close	Close	Close	Close	Open	Open	Open

(ㅇ 입장에서 ㄱ과 ㅁ은 Close되었음으로 ㅈ가 갱신시 더 작아짐으로 ㅈ을 갱신한다.)

 

6번째 반복.

Index	ㄷ	ㄱ	ㅁ	ㅎ	ㅇ	ㄴ	ㅅ	ㅈ
From	-1	ㄷ	ㄷ	ㄷ	ㅁ	ㅁ	ㄴ	ㅇ
F	0	10	15	20	20	25	28	35
State	Close	Close	Close	Close	Close	Close	Open	Open

(ㄴ과 연결된 것 은 Close된 ㅁ과 Open된 ㅅ밖에 없음으로 ㅅ를 갱신한다.

 

7번째 반복.

Index	ㄷ	ㄱ	ㅁ	ㅎ	ㅇ	ㄴ	ㅅ	ㅈ
From	-1	ㄷ	ㄷ	ㄷ	ㅁ	ㅁ	ㄴ	ㅇ
F	0	10	15	20	20	25	28	35
State	Close	Close	Close	Close	Close	Close	Close	Open

(28에서 10을 더해도 35보다 커짐으로, ㅈ을 갱신하지 못한다. 닫기만 하고 종료)

 

8번째 반복.

Index	ㄷ	ㄱ	ㅁ	ㅎ	ㅇ	ㄴ	ㅅ	ㅈ
From	-1	ㄷ	ㄷ	ㄷ	ㅁ	ㅁ	ㄴ	ㅇ
F	0	10	15	20	20	25	28	35
State	Close	Close	Close	Close	Close	Close	Close	Close

(목표점에 도착하였음으로, 모든Node가 Close가 되었기 때문에, 탐색이 종료된다.)

 

 

8번의 탐색으로 모든 노드가 탐색 완료되었다.

 

이제 역순으로 진행하면 된다.

ㅈ의 연결은 ㅇ 이고, ㅇ의 연결은 ㅁ ㅁ의 연결은 ㄷ 임으로,

 

ㄷ->ㅁ->ㅇ->ㅈ 순으로 나오는 Cost 35가 최소한의 거리가 된다고 계산결과가 나타난다.

 

이렇게 계산되는것이 Dijkstra 알고리즘 이다.