20210810 Dijkstra(다익스트라) 알고리즘

안녕하세요 틴구입니다

이번 글은 Dijkstra 알고리즘에 관한 설명입니다

1.Dijkstra 정의

a정점과 b점점 사이의 최단 경로를 찾는 데이크스트라의 알고리즘입니다.

가장 낮은 값을 가진 방문하지 않은 꼭짓점을 선택하고,
방문하지 않은 각 인접 노드와의 거리(가중치)를 계산하고,
작을 경우 인접 거리를 업데이트하는 개념입니다.

 

단, 음의 가중치가 없는 그래프여야 하고, 방향 그래프, 무방향 그래프 모두 상관없습니다.

 

2. 이론 설명

위와 같이 1번부터 5번까지의 노드가 있고 그를 연결해주는 엣지와 엣지의 가중치값(Cost)이 있다고 가정을 한다.

이때 처음 시작지점인 1번 노드의 시작 값은 0으로 지정해둔다

여기서 1번에서 4번까지 가는 최단 루트를 구한다고 가정을 했을 때

1번 노드에서 연결되는 2번 노드와 5번 노드를 연결하는데 이때 각 노드의 코스트 값들은 무한대(ex) INT_MAX)로 두어가지고 1번 노드에서 2번 노드까지 갈 때 필요한 값을 더한 뒤 더한 값이 2번 노드의 값보다 작으면 2번노드의 값을 갱신해주는 형식입니다

 

ex)_ (1번 노드의 시작 값 0)  - (2번 노드까지 가는 가중치 3) < 2번 노드의 값이라면

2번 노드의 값 = 1번 노드의 시작 값 0  - 2번 노드까지 가는 가중치 3으로 갱신해주는 개념입니다.

 

5번 노드도 마찬가지로 1번 노드의 값 + 5번 노드로 가는 가중치 값 < 5번 노드의 값 INT_MAX는 true기 때문에

5번 노드는 4의 값을 갖게 되는 겁니다.

 

그다음 2번에서는 1번과 3번과 4번 노드를 연결할 수 있는데

1번 노드의 경우는 기본값이 0인데 돌아가면 3 + 3 이기 때문에 패스

3번 노드는 3 + 2 가 3번 노드의 INT_MAX보다 작기때문에 3번노드 = 5로 갱신

4번 노드는 3 + 1 이 4번 노드의 INT_MAX보다 작기떄문에 4번노드 = 4로 갱신

 

다음 3번 노드에서 4번 노드로 갈 때 5 + 1 가 위에서 4번 노드의 값을 갱신한 4보다 크기 때문에 패스

 

다음은 5번 노드를 봅시다 5번 노드에서 4번 노드까지 가는데 가중치가 2이기 때문에

5번 노드의 값이었던 4 + 2가 4번 노드가 위에서 INT_MAX에서 4로 바뀌었던 값보다 크기 때문에 패스

 

결국 최단 루트는 1 - 2 - 4가 되는 것입니다.

 

3. 코드 구성

 

기본 코드 구성(생성자, 소멸자, 필요한 데이터들)은 이렇게 구성이 되어 있습니다.

그래프 자료구조와 동일한 구성인데 class CDijkstraNode에 가중치와 부모 노드가 필요하기 때문에 m_Cost, m_Parent만 추가해준 겁니다.

 

void AddEdge(CDijkstraNode<T>* Node, int Cost) 함수

그래프 코드의 AddEdge와 동일한데 여기서 m_Cost의 값만 추가한 코드 구성입니다.

void insert(const T& data) 함수

위의 코드는 그래프 자료구조의 코드와 동일합니다

m_Size가 총공간이랑 같으면 늘려주고 노드의 인덱스에 값들을 넣어주는 방식입니다.

 

void AddEdge(const T& Src, const T& Dest, int Cost)는

insert에서 만들어준 노드로 연결해줄 노드들을 정해주는 함수입니다.

Graph 코드와 동일한데 인자에 Cost만 추가로 넣어줍니다.

다음은 FindNode 함수입니다 이 함수는

a번의 노드에서 b번의 노드까지의 최단거리를 알고자 할 때

각 노드들의 주소를 알기 위한 함수입니다.

SortNode함수와 Add함수는 아래의 사진 참고

class CDijkstraNode에다가 Add(CHeap<CEijkstraNode<T>*>& heap)을 구성해준다.

자세한 설명은 주석으로 달려있으니 생략하겠습니다.

class CDijkstra에다가 static bool SortNode함수를 만들어줍니다.

위 함수는 정렬을 해주기 위한 함수입니다.