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

다익스트라 알고리즘

다익스트라 알고리즘은 다이나믹 프로그래밍(DP)과 그리디 알고리즘을 활용한 최단경로 탐색 알고리즘이다. 다익스트라 알고리즘은 하나의 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 알 수 있으며, 간선의 가중치가 양수일 때 사용가능하다.

다익스트라 알고리즘이 DP라고 할 수 있는 이유는 특정 최단 거리는 여러 개의 최단거리로 이루어져 있기 때문이며, 하나의 최단 거리를 구할 때 특정 정점까지의 최단거리 정보를 그대로 가져와 사용하기 때문이다. 또한 그리디 알고리즘이라고 말할 수 있는 이유는 특정 최단 거리에 최단 거리를 더해가며 최종적인 최단거리를 계산하는 방식이기 때문이다. (다익스트라 알고리즘을 공부한 뒤 다시 읽으면 쉽게 이해가능)

한 정점에서 다른 모든 정점까지의 최단거리를 반복해서 계산하며 갱신하기 때문에 한 정점당 N(정점수)개의 요소를 가지고 있는 배열이 필요하다. 결국 모든 정점 입장에서 최단거리를 계산하려면 N*N의 2차원 배열을 사용할 수 있다. 아래의 표를 해석해 보면 2번 정점에서 4번 정점까지의 최단거리는 7(경로 : 2→1→3→4)이고 3번 정점에서 2번 정점까지의 최단거리는 6(경로 : 3→1→2)이다.
(다익스트라는 결론적으로 아래의 표를 만들어내는 것을 목표로 하는 알고리즘이다.)

각 정점에서 다른 정점까지의 최단거리를 나타낸 2차원 배열

 

다익스트라 알고리즘 과정

1. 시작정점 선택
2. 거리 배열 초기화 (시작정점은 0으로 다른 노드는 무한대로)
3. 지금까지 방문하지 않은 정점 중 가장 짧은 거리를 가진 정점 방문
4. 현재 방문한 정점과 인접한 정점들의 거리 값을 갱신
5. 단계 3과 4를 반복

시작 정점: 1

거리 배열 초기화

시작 정점을 1로 선택한 후 거리 배열을 초기화한다. 특정 노드에서 다른 모든 노드까지의 최단거리를 저장할 배열이기 때문에 자신 포한 N개의 크기의 배열을 만든다. 자기 자신은 0으로 나머지는 무한대(inf, ∞)로 초기화하는데 무한대의 의미는 두 정점이 직접 연결되어있지 않다는 뜻이다.

 

가장 짧은 거리를 가진 정점 방문

방문하지 않은 정점 중 현재 거리 배열에서 가장 짧은 값을 가진 정점을 선택해 방문한다. 현재는 아무 정점을 방문하지 않은 상태이고 거리 배열에서 0의 값을 가진 1번 정점이 가장 짧은 값을 가지고 있기 때문에 1번 노드를 방문한다.

 

인접한 정점의 거리값 갱신

현재 정점에서 인접한 정점들의 배열값을 갱신해 준다. 업데이트 식은 dist[인접정점] = min(dist[인접정점], dist[현재정점] + cost(현재정점🠒인접정점)) 으로 cost(현재정점🠒인접정점)은 현재 정점에서 해당 인접정점까지 거리(가중치)이다. 이 식을 의미적으로 생각해 보면, 현재 시작정점에서 해당 인접정점까지의 최단거리가 배열에 저장되어 있는데 그 값과 현재 방문한 정점을 거쳐 가는 경로의 비용과 비교하여 더 짧은 비용으로 갱신해 준다는 뜻이다. 현재 정점에서 인접한 정점들만 갱신해 주는 이유는 인접하지 않은 정점들은 cost(현재정점🠒인접정점)가 어차피 무한이 되기 때문에 현재 배열에 담긴 값이 최단 거리가 될 것이기 때문이다.

현재 방문한 정점 1에서 인접한 정점 2, 3, 4에 대한 배열값을 갱신한다. 현재 단계는 시작정점과 현재정점이 같아서 인접한 정점들에 대한 간선 값이 그대로 갱신되었는데, 다음 정점부터는 의미적으로 파악하기 쉬울 것이다.

dist[2] = min(dist[2], dist[1] + cost(1🠒2)) = min(∞, 0+4) = 4
dist[3] = min(dist[3], dist[1] + cost(1🠒3)) = min(∞, 0+2) = 2
dist[4] = min(dist[4], dist[1] + cost(1🠒4)) = min(∞, 0+7) = 7

 

다음 정점 방문 - 배열 갱신 반복

현재 정점 선택 (3)

인접 정점 1과 4에 대해 갱신여부 확인

다음 방문 정점은 방문하지 않은 정점 중 거리가 가장 짧은 정점 3으로 선택한다. 그리고 배열의 갱신은 정점 3에 인접한 정점 1과 4 중에 방문하지 않은 4에 대해 진행한다. 인접한 정점 1에 대해 계산을 하지 않는 이유는 이미 방문한 정점은 최단거리가 구해져 있기 때문에 무의미한 계산이 된다.

dist[4] = min(dist[4], dist[3] + cost(3🠒4)) = min(7, 2+4) = 6

정점 4에 대해 살펴보면, 배열에 저장된 현재까지 최단거리인 7보다 dist[3] + cost(3🠒4)의 값이 6으로 더 작아 갱신되었다. 의미적으로 보면 지금까지 계산한 시작정점 1에서부터 정점 4까지의 최단거리보다 (경로는 어떻든 비용이 저장되어 있음) 현재 정점 3을 거처 4까지 이동하는 경로가 비용이 더 적다는 것을 의미한다. 따라서 시작 정점 ~ 현재 정점까지의 비용에 현재 정점 ~ 인접 정점까지의 비용을 더한 값으로 갱신해 준다.

 

 

현재 정점 선택 (2)

인접 정점 1과 3에 대해 갱신여부 확인

방문하지 않은 정점 중 가장 값이 작은 정점 2를 방문하였고 정점 2의 인접 정점인 1과 3은 이미 방문하여 최단거리를 구한 정점이기 때문에 갱신 없이 다음 정점으로 넘어간다.

 

 

현재 정점 선택 (4)

방문하지 않은 정점 4를 방문하였고 더 이상 갱신할 정점이 없어 종료된다.

위의 과정을 통해 시작 정점 1에서 다른 모든 정점까지의 최단 거리를 구할 수 있게 되었다. 모든 정점에 대해 최단거리를 다익스트라 알고리즘을 통해 구하고자 한다면 시작 정점을 2, 3, 4로 바꾸어가며 위의 과정을 반복하면 된다.

 

 

그림에서 예시로 든 그래프는 백준의 1238번 파티의 예제에서 가져왔다. 해당 문제를 풀어보면 다익스트라 알고리즘을 이해하는데 도움이 될 거다. (업데이트 과정이 많은 그래프로 예시를 들걸...)