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

다익스트라 알고리즘(Dijkstra Algorithm)은 다이나믹 프로그래밍을 활용하는 대표적인  최단 경로를 찾는 알고리즘이다. 다만 다익스트라 알고리즘은 음의 간선을 포함할 수 없다. 즉, 음의 간선이 하나라도 포함되어 있다면, 다익스트라 알고리즘을 사용할 수 없다. 원래 다익스트라 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이다. 하지만, 일반적으로 한 꼭짓점을 루트(root) 꼭짓점으로 고정하고, 그래프의 다른 모든 꼭짓점까지의 최단 경로를 찾는 알고리즘으로 최단 경로 트리를 만든다. 

동작 단계

1. 출발 노드를 설정한다.
2. 최단 거리를 저장할 테이블을 초기화해준다.(보통 무한대(아주 큰 값)로 초기화한다.)
3. 현재 위치하고 있는 노드의 인접 노드 중 비용이 가장 적은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 3 ~ 4의 과정을 반복한다.

예시를 보며 과정을 확인해보자. 

위와 같은 그래프가 있다고 하자.

표는 최단 거리 테이블을 INF로 초기화한 후, 특정 노드에서 다른 노드로 갈 때의 비용을 저장한 것이다.

시작 노드를 1로 설정한 후, 다익스트라 알고리즘을 수행해보자.

노드 1을 선택했을 때 다른 정점으로 가는 최소 비용은 위와 같다.

현재 방문하지 않은 노드 중 비용이 가장 적은 2번 노드를 선택한다.

2번 노드를 선택하기 전 3번 노드로 가는 비용은 INF(무한)이었다.

하지만 2번 노드를 선택함에 따라 1번 노드에서 2번 노드를 거쳐 3번으로 가는 경로가 생겼으므로 6을 갱신해준다.

또한, 1번에서 5번으로 바로 가는 방법이 아닌, 1번 노드에서 2번 노드를 거쳐 5번으로 가는 방법도 있다.

지금은 두 과정의 비용이 같으므로 갱신하지 않지만, 2번 노드를 거쳐 5번으로 가는 비용이 더 적다면 갱신해야 한다.

 

또 다시 방문하지 않은 곳 중에서 비용이 가장 작은 노드를 선택한다.

따라서 5번 노드가 선택된다.

5번 노드를 선택함으로써 5번 노드를 거쳐 4번 노드와 6번 노드로 갈 수 있게 되었다.

5번을 거쳐 4번 노드로 가는 비용은 10이다. 여태 4번 노드로 가는 비용은 INF였으므로 10으로 갱신해준다.

6번 노드로 가는 비용 또한 원래는 INF였으나, 5번을 거쳐감으로써 7이 되므로 갱신해준다.

 

방문하지 않은 노드 중 가장 작은 간선으로 갈 수 있는 곳은 3번 노드이다.

3번 노드를 선택하자.

3번 노드를 거쳐 4번 노드로 가는 최소 비용은 9이다. 5번 노드를 거쳐 4번 노드로 갈 때 10이었던 비용보다 적은 비용이므로 갱신해준다.

 

계속해서 과정을 진행시켜보자......

이제 척 보면 척일 것이다.

비용이 가장 적은 6번 노드를 선택하자.

7번 노드로 가는 길이 열렸다.

최소 비용은 9가 된다.

 

두 간선이 최소 비용이다.

이 때는 아무 노드나 선택해주면 되지만, 나는 구현할 때 우선순위 큐를 사용할 것이기에, 4번 노드가 먼저 선택될 것이다.

4번을 거쳐 7번으로 가는 비용은 12로, 6번을 거쳐 7번으로 가는 비용보다 크다. 따라서 갱신되지 않는다.

4번을 거쳐 8번으로 가는 길이 열렸다. 비용은 11로 INF보다 작으므로 갱신된다.

 

곧 끝난다!

이번엔 비용이 적은 7번 노드가 선택된다.

7번 노드를 거쳐 8번 노드로 가는 비용은 10이다. 4번을 거치는 것보다 더 적은 비용으로 이동 가능하므로 갱신해준다.

다음으론 남은 노드가 한개 뿐이므로 8번 노드가 선택된다.

 

모든 노드를 방문했으므로 다익스트라 알고리즘을 종료한다.

마지막 과정의 표에 있는 값들이 1번 노드부터 특정 노드까지 이동하는데 필요한 최소 비용이 된다.

구현

다익스트라 알고리즘을 구현하는데에는 두가지 방법이 있다.

• 순차 탐색
• 우선 순위 큐

순차 탐색을 사용하면, 노드의 개수에 따라 탐색 시간이 매우 오래 걸릴 수 있다.

이를 개선하기 위해 도입된 것이 우선순위 큐이다.

import java.util.*
import kotlin.collections.ArrayList

private const val nodeCnt = 8
private const val edgeCnt = 11
val graph = Array(nodeCnt + 1) { ArrayList<Pair<Int, Int>>() }

data class EdgeInfo(val node: Int, val cost: Int): Comparable<EdgeInfo> {
    override fun compareTo(other: EdgeInfo): Int = cost - other.cost
}

fun main() = with(System.`in`.bufferedReader()) {
    for(i in 0 until edgeCnt) {
        val (from, to, cost) = readLine().split(" ").map { it.toInt() }
        graph[from].add(Pair(to, cost))
        graph[to].add(Pair(from, cost))
    }

    val arr = dijkstra(1)
    repeat(nodeCnt) { i -> print("${arr[i+1]} ")}
}

private fun dijkstra(start: Int): IntArray {
    val cost = IntArray(nodeCnt + 1)
    repeat(nodeCnt + 1) { i -> cost[i] = Int.MAX_VALUE }

    val pq = PriorityQueue<EdgeInfo>()
    pq.add(EdgeInfo(start, 0))
    cost[start] = 0

    while(pq.isNotEmpty()) {
        val cur = pq.poll()
        val curNode = cur.node
        val curCost = cur.cost

        for(i in 0 until graph[curNode].size) {
            val nextNode = graph[curNode][i].first
            val nextCost = curCost + graph[curNode][i].second

            if(nextCost < cost[nextNode]) {
                cost[nextNode] = nextCost
                pq.add(EdgeInfo(nextNode, nextCost))
            }
        }
    }

    return cost
}