2021-01-06

다익스트라(Dijkstra)

다익스트라(Dijkstra)는 거리를 기준으로 하는 우선순위 큐를 이용하여 하여 최단 거리를 측정한다.
written by

Introduction

현재 지점에서 모든 지점에 대한 최단 거리를 알아내는 알고리즘.

원리는 지극히 단순한데 매 순간 기존의 거리와 지금의 거리를 비교해서 더 짧은 거리를 기록하는 방식이다. 가능한 모든 경로를 조사한 후에 해당 지점에 기록된 거리가 최단 거리가 될 것이다. 다음의 순서대로 기록한다.

  • 기록된 거리가 없으면 해당 지점까지의 이동 거리를 기록한다.
  • 기록된 거리가 있으면 해당 지점까지의 이동 거리를 비교해서 더 짧은 거리를 기록한다.
  • 모든 지점을 방문할 때까지 위의 과정을 반복한다.

Algorithm

다익스트라(Dijkstra)는 매 순간의 최단 거리를 측정해야 하므로 순서가 중요하다. 따라서 각각의 순간에서 가장 짧은 거리부터 방문하는 것이 연산을 줄이는데 좋다. 거리를 기준으로 하는 우선순위 큐를 이용하여 다음의 순서대로 진행한다. 출발 지점은 거리를 0으로 기록하고, 나머지 지점은 무한대를 나타내는 임의의 거리를 기록한 후에 우선순위 큐에 출발 지점을 넣는다.

  • 우선순위 큐의 헤드에 있는 지점에서 방문이 가능한 지점들을 방문한다.
  • 해당 지점에 기록된 거리가 없으면 해당 지점까지의 이동 거리를 기록한다.
  • 해당 지점에 기록된 거리가 있으면 이동 거리가 작을 경우만 이동 거리를 기록한다.
  • 거리가 갱신된 경우에만 해당 지점과 해당 지점에 기록된 거리를 우선순위 큐에 넣는다.
  • 큐에서 헤드를 제거한다.
  • 큐가 빌 때까지 위의 과정을 반복한다.

Kotlin Scratch 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),
)

// 현재 위치 인덱스.
val location = 0

// 거리를 저장하는 배열, 시작 인덱스의 값만 0으로 만들고, 나머지는 무한대를 표현할 수 있는 임의의 값을 저장한다.
// 합 연산시에 오버플로가 발생할 수 있으므로 여유분을 감산하였다.
val distances = Array(map.size) { i -> if (i == location) 0 else Int.MAX_VALUE - 100 }

// 첫 번째 값은 인덱스, 두 번째 값은 거리인 페어에서 거리를 기준으로 방문할 순서를 결정하는 우선순위 큐를 만든다.
val mapQueue = PriorityQueue<Pair<Int, Int>>(compareBy { it.second }).apply { add(Pair(location, 0)) }

// 가능한 모든 경로를 탐색한다.
while (mapQueue.isNotEmpty()) {

    // 큐의 헤드에 있는 지점으로부터 방문이 가능한 모든 지점을 방문한다.
    map[mapQueue.element().first].forEachIndexed { i, distance ->

        // 최단 거리를 비교하기 위한 현재까지의 거리.
        val distanceToCompare = distances[mapQueue.element().first] + map[mapQueue.element().first][i]

        // 현재 지점에서 연결된 곳을 방문하면서, 최단 거리를 갱신한다.
        // 갱신할 거리가 기존 최단 거리보다는 작아야 갱신할 가치가 있다.
        // 그렇지 않으면 방문할 가치가 없으므로 방문할 우선순위 큐에는 삽입하지 않는다.
        if (distance != 0 && distances[i] > distanceToCompare) {
            distances[i] = min(distances[i], distanceToCompare)
            mapQueue.add(Pair(i, distances[i]))
        }
    }

    // 큐에서 방문한 곳을 제거한다.
    mapQueue.poll()

    // distances 변화 과정을 출력한다.
    // 갱신되지 않는 곳은 X로 표기하고, 마지막까지 X인 경우는 방문이 불가능한 곳이다.
    println("--------------------")
    distances.forEach { println(if (it != Int.MAX_VALUE - 100) 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