[Algorithm] 다익스트라(Dijikstra) 알고리즘

■ 배경 

 그래프의 탐색 알고리즘 중 BFS가 가볍고 구현하기 쉽다는 것을 알 수 있었다. 하지만 BFS의 단점은 아래 두 가지의 단점이 있다. 

 

(1) 목적지를 모른다. 그러므로 접근 가능한 모든 정점을 탐색한다.

(2) 가장 먼저 발견한(Discovered) 정점들을 방문 예약한다.

 

다익스트라 알고리즘은 위에서 (2) 문제를 해결하기 위해 고안된 알고리즘이다.

■ 특징

먼저 가중치 그래프를 활용하고 일반적인 큐(Queue)를 사용하는 BFS와 달리 우선순위 큐(Priority Queue)를 사용한다.

가중치 그래프 (Weighted Graph)

 

(+)=====

우선 순위 큐는 아래 포스팅에 서술 및 구현해봤었다.

https://yjhdevelopdiary.tistory.com/193

[자료구조] 우선 순위 큐 (Priority Queue)

======

 

우선 순위 큐를 사용하는 이유는 BFS와 달리 먼저 발견한 정점들을 기록해놓되 저장은 하지않고 나중에 가중치 값이 가장 낮은 Best Case를 사용하기 위해서이다.

 

쉽게 말해 가중치 값(Cost)를 '거리'라고 생각한다면 거리가 짧은 루트를 이용해 도착지에 빨리 도착하길 누구나 원할 것이다. 그로 인하여 가장 낮은 값을 가장 빠른 속도로 반환해줄 수 있는 우선 순위 큐를 사용하게 되었다.

■ 코드

먼저 정점 데이터와 부모로부터 소요되는 비용(cost)을 내포하고있는 구조체를 하나 정의하고

 

메인 함수에서 차례대로 (1) 그래프 생성 (2) 알고리즘 실행을 진행한다.

 

그래프 생성 코드는 이전과 크게 다를 것 없다. 위 예시 그래프를 기준으로 비용이 얼마나 되는지 기록해놨고

 

이후 다익스트라 함수로 들어간다. 우선순위큐(priority queue) 변수를 만들어놓는다.

(1) 첫번째 인자로 VertexCost 타입 데이터를 담을 것이라는 것을 알려주고

(2) 두번째 인자로 vector 컨테이너를 사용하겠다고 알린다.

(3) 조건식(Predicate)은 A > B (Greater)를 사용한다. Less가 더 작은 값이 아래로 내려가는 것이었다면 반대로 Greater은 더 작은 값이 부모로 있어야하고 최소값이 루트에 존재해야한다.

 

best 가중치 값을 저장하고 있을 벡터 컨테이너와 부모 정점 인덱스를 담고있을 벡터 컨테이너를 선언하였다. 맨 처음 값 0번째 정점은 항상 부모가 자기 자신이고 best case는 출발점이기에 0으로 고정이다.

 

그 이후 우선순위가 비어질 때까지 while 반복문 유지한다. 

 

(1) 먼저 BFS와 동일하게 첫번째 정점이 가장 발견한 두 정점의 데이터 (15, 1)과 (35, 3)를 잠시 우선순위 큐에 기록한다.

(2) 그러고나서 정점1에 인접한 정점2와 정점3으로 가는 cost 및 정점 인덱스 데이터 (20, 2) (25, 3)를 기록한다.

또한 이전에 best[3]에 기록해놓은 정점3으로 가는 비용인 35 값보다 현재 발견한 루트의 비용(25)이 더 낮으므로 데이터를 덮어씌운다.

▼ 정점2로 가는데 필요한 비용 (15+5)

▼ 정점3으로 가는데 필요한 비용 (15+10)

 

▼ (현재 상태) best값이 바뀐 것을 볼 수 있다. best값이 항상 바뀔 수 있다는 것이 중요하다.

 

이를 계속 반복하다보면 정점4를 만난뒤 정점5로 향하기 전에 우선 순위 큐에 들어가 있는 데이터 상태는 아래와 같다.

best[3]에 들어가있는 비용이 25이고 맨 처음에 기록한 데이터의 비용은 35이므로 자연스럽게 (35, 3)의 데이터는 pop을 통해 제거된 후 아무런 행동 없이 넘어가게된다.

 

▼ 마지막에 Best 경로에 들어가는 가중치 비용을 콘솔창에 띄워봤다. 의도대로 작동한다.

 

 

■ A* 알고리즘...

▼ 하지만 다익스트라(Dijikstra)를 구현하고도 BFS의 문제점 (1)은 해결하지 못했다.

(1) 목적지를 모른다. 그러므로 접근 가능한 모든 정점을 탐색한다.

 

이런 단점을 해결하기 위하여 고안된 것이 바로 A*알고리즘이다.

 

 

■ 참고 및 추천 (★)

https://www.inflearn.com/course/%EA%B2%8C%EC%9E%84-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8-%EC%9E%85%EB%AC%B8-%EC%98%AC%EC%9D%B8%EC%9B%90-rookiss/dashboard 

[게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows API & 게임 서버