다익스트라(Dijkstra) 간단 정리 [컴공과고씨]

 백준을 풀다보면 마주하는 최단 경로 탐색 알고리즘 다익스트라이다.

다이나믹 프로그래밍을 활용한 알고리즘으로 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다.

다만 이때 음의 간선을 포함하면 안된다. 간선에 음수가 포함 되어있을 때에는 벨만-포드 알고리즘을 사용해야하는데 이것은 나중에 다루어 보고 일단 다익스트라에 대해서 살펴보자.

 

 핵심은

1. 목표 정점까지의 최단 거리는 여러개의 최단 거리로 이루어져있다.

2. 그래서 하나의 최단 거리를 구할 때 그 전까지 최단거리를 이용해준다.

먼저 선언해주어야 하는 것이 우선순위 큐, 각 정점까지의 거리를 담을 dst[] 배열이다.

우선순위 큐는 다음 정점의 번호와, 다음 정점까지 거리를 담고 있고 다음 정점까지 거리를 최소로 하는 것이 루트로 갈 수 있도록 선언해준다. dst[]배열 같은 경우 초기 값을 INF(가장 큰 값)으로 초기화 해준다.

 

0에서 5번 정점까지 간다고 할 때 다익스트라로 계산을 해본다면

자 우선순위 큐에 들어가기 위한 조건은 현재 정점까지의 거리와 다음 정점까지 거리를 합했을 때 다음 정점의 dst 값보다 작으면 넣을 수 있다.

 

그럼 처음에 0번 정점에서 시작한다면 우선순위 큐에 0(시작 정점)과 0 (현재 정점까지 거리)를 넣고 시작한다.

while문을 들어간 후 큐 루트에 있는 정점과 거리를 가져오고 pop을 해준다.

그 후 for문을 통해 0번과 이어진 정점들과 거리를 큐에 넣어준다.

이 때 조건문에는 

1번 정점까지의 경우 현재 정점까지 거리 = 0 + 다음 정점까지는  = 1 -> 총 1

dst값은 INF 이므로 dst[1]에는 1이 기록되고 우선순위 큐에 1(다음 정점번호) 와 1(정점 1까지의 거리) 가 들어가게 된다.

마찬가지로 2번 정점, 3번 정점도 조건을 통과하여 들어가게 된다.

현재까지  상황 큐에 (1,2,3 정점), dst[1] = 1, dst[2] =2, dst[3] =3.

위 그림과 같은 그림

다음 반복에는 

먼저 큐에 담긴 거리가 가장 작은 1번 정점이 큐에서 나오게 된다. (pop)

for문에 들어가 1번과 이어진 정점 추출 후 조건에 맞는 것들 큐에 넣어줌.

2번 정점으로 가는 길인 경우 현재 정점까지 거리 = 1 + 2번으로 가는 길까지의 거리 = 3 -> 총 4 

현재 dst[2] = 2 이므로 현재 dst[2]가 더 작으므로 큐에 넣지 않음.

5번으로 가는 길은 총 거리가 8, dst[5]가 INF이기 때문에 큐에 넣어줌.

 

그 다음 반복에는 큐에 들어있는 거리 중 가장 짧은 2번 정점이 나옴 마찬가지로 큐에 넣을 정점들을 보면

dst[5]까지 거리가 현재 8인데 2번에서 총 거리는 6으로 계산이 되므로 dst[5]에 6을 넣어주고 큐에 넣어줌

그 다음 반복에는 3번 정점이 또 그 다음 정점에는 4번 정점이 4번 정점에서 dst[5]가 5로 업데이트 되고 큐에 들어가게 되고 결국 5번까지 최단 거리가 dst에 기록되면서 반복문이 끝나게 된다.

여기서 결과적으로 dst배열에는 0번으로 부터 각 정점까지의 최단거리가 남게 된다. 

 

이정도로 이해하고 밑에 백준 문제를 한번 풀어보고 코드를 보면 더욱더 이해가 쉽다.

https://hagisilecoding.tistory.com/135 다익스트라를 이용한 백준 문제 풀이 (1238 파티)