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

1.개요

 드디어 다익스트라 알고리즘 구현을 끝냈다. 이 알고리즘을 연구하고 구현하는데 4일 정도가 소요된 것 같다. 다른 사이트들을 참고하면서 나만의 코드 스타일로 만들기 위해서 많은 노력을 했다.  다익스트라 알고리즘은 방향성과 가중치가 있는 그래프에서 최단거리를 구하는 알고리즘이다. 이번 다익스트라는 정점을 단순히 int값이 아닌 string값으로 입력받아 출력해주는 것을 목표로 구현했다. 다익스트라는 우선순위 큐를 이용해서 구현하는 것이 핵심이다. 방문한 정점에 인접한 정점들을 전부 우선순위 큐에 넣고 작은 가중치로 정렬된 우선순위 큐에서 빼내면서 최단거리를 구한다. 물로 그냥 큐를 사용해도 최종적으로는 최단거리로 갱신이되지만 우선순위 큐를 사용하면 이 갱신하는 작업을 없앤다.

 다익스트라는 유명한 커머스 회사에서 나온 문제이기도 하기에 시간을 들여서 정복하기로 마음먹고 파헤치기 시작했다. 시간은 오래걸린거 같기도 하지만 그만큼 이해도가 높아졌다 생각하자. 

 

2.문제

 - Black에서 Blue지점까지 가는 최단 거리를 다익스트라를 이용해서 구하라.

3.구현

1) 그래프 만들기

 위 그림과 같이 리스트로 그래프를 만들었다.

2) 구조체 설명

 - Vertex: vertex(부모와 연결된 vertex이름), weight(부모와 연결된 가중치), next(다음 노드)

 - Adj: head(인접한 vertex를 가르키는 포인터), cur(이 포인터는 각각의 vertex를 가르키며 이동하는 포인터임)

 - Graph: vertexCnt(정점 개수), edgeCnt(엣지 개수), unorder_map<string, Adj *> map(1번 그림을 나타내는 변수)

 - Comp: 우선순위 큐의 비교 연산자 재정의(오름차순)

3) 흐름

 - 'From'을 입력 받고 Graph 구조체의 map 변수에 'From'값이 있는지 확인

 - 'From' 값이 없다면 map에 추가

 - 'To'를 입력 받고 Graph 구조체의 map 변수에 'To' 값이 있는지 확인

 - 'To' 값이 없다면 map에 추가

 - unorder_map<string, string> path: [방문한 정점, 이전에 방문한 정점], 이 변수는 방문한 경로를 나타내는 변수로 사용한다. 이전에 방문한 변수를 저장하여 스택에 넣고, 꺼내면서 출력하면 방문한 경로가 나옴

 - unorder_map<string, int> distance: [방문한 정점, 최소 가중치], 이 변수로 출발 지점에서 방문한 지점까지의 최단거리를 저장

4.코드

5.결과

참고자료

---

http://makefortune2.tistory.com/26

http://hsp1116.tistory.com/42