2021-01-06

다익스트라(Dijkstra)

시작점으로부터 해당 지점까지의 최단 거리를 알아내는 알고리즘이다. 내비게이션에서 최단 거리를 구하는데 사용할 수 있다.
written by

시작 지점부터 모든 위치의 최단 거리를 구하기

시작점으로부터 해당 지점까지의 최단 거리를 알아내는 알고리즘이다. 내비게이션에서 최단 거리를 구하는데 사용할 수 있다. 방식은 시작 지점부터 가장 거리가 짧은 연결된 곳을 방문하면서 현재까지의 최단 거리를 기록해가는 방식이다. 그래서 매번 거리가 가장 짧은 순서대로 방문하는 것이 핵심이다. 그래서 거리를 기준으로 하는 우선순위 큐를 사용한다.

Kotlin Code

import java.util.*
import kotlin.math.min

// map[a][b] = distance, a 지점에서 b 지점까지의 거리를 기록한 이차원 배열.
private val map = listOf(
    listOf(0, 0, 6, 3, 0),
    listOf(3, 0, 0, 0, 0),
    listOf(0, 0, 0, 2, 0),
    listOf(0, 1, 1, 0, 0),
    listOf(0, 4, 0, 2, 0),
)

// 거리를 저장하는 배열, 시작 인덱스의 값만 0으로 만들고, 나머지는 무한대를 표현할 수 있는 임의의 값을 저장.
val dist = Array(map.size) { i -> if (i == 0) 0 else Int.MAX_VALUE }

// 방문할 순서를 결정하는 우선순위 큐, 거리를 기준으로 우선순위 큐를 만든다.
val priorityQueue = PriorityQueue<Pair<Int, Int>>(compareBy { it.second }).apply { add(Pair(0, 0)) }

// 방문할 곳이 더 이상 없을 때까지 큐를 탐색.
while (priorityQueue.isNotEmpty()) {

    // 큐의 헤드로부터 현재 위치를 방문한다.
    map[priorityQueue.element().first].forEachIndexed { index, item ->

        // 현재 위치에서 연결된 곳을 방문하면서, 최단 거리를 갱신한다.
        // 갱신할 거리가 기존 최단 거리보다는 같거나 작아야 방문할 가치가 있다.
        // 그렇지 않으면 방문할 가치가 없으므로 방문할 우선순위 큐에 삽입하지 않는다.
        // 방문하여 연결된 곳의 최단 거리의 갱신이 끝나면 큐에서 방문한 곳을 제거한다.
        if (item != 0 && dist[index] >= dist[priorityQueue.element().first] + map[priorityQueue.element().first][index]) {
            dist[index] = min(
                dist[index],
                dist[priorityQueue.element().first] + map[priorityQueue.element().first][index]
            )
            priorityQueue.add(Pair(index, dist[index]))
        }
    }.run { priorityQueue.poll() }

    // 매회 dist 변화 과정을 프린트한다.
    // 갱신되지 않는 곳은 X로 표기한다.
    // 마지막까지 X인 경우는 방문이 불가능 한 곳이다.
    println("--------------------")
    dist.forEach { println(if (it != Int.MAX_VALUE) it else "X") }
    println("--------------------")
}

Result

--------------------
0
X
6
3
X
--------------------
--------------------
0
4
4
3
X
--------------------
--------------------
0
4
4
3
X
--------------------
--------------------
0
4
4
3
X
--------------------
--------------------
0
4
4
3
X
--------------------
2021 © Cinntiq's Studio