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

개발/알고리즘

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

스몰스테핑 2024. 9. 11. 14:15

1. 다익스트라 알고리즘이란?

이 알고리즘은 에츠허르 데이크스트라가 1956년에 고안하고 1959년에 발표되었다. 그의 이름에서 따와 데이크스트라, 다익스트라라고 불리우는 이 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다.

최단 경로 탐색 알고리즘으로 널리 알려져있으며, 흔히 인공위성 GPS 소프트웨어 등에서 가장 많이 사용된다.

특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려주기 때문에 음의 간선을 포함할 수 없다. 물론 우리가 살아가는 현실은 음의 간선이란 존재하지 않기에 다익스트라 알고리즘은 현실 세계에서 사용하기 매우 적합한 알고리즘 중 하나라고 할 수 있다.

다익스트라 알고리즘은 하나의 정점에서 모든 정점으로 가는 최단 경로를 알려준다면, 플로이드-워셜 알고리즘은 가능한 모든 정점 쌍들에 대한 최단 거리를 구하는 알고리즘이다.

다익스트라 알고리즘을 확장시킨 알고리즘이 A* 알고리즘이다. 이 외에도 벨만-포드 알고리즘, 플로이드-워셜 알고리즘 또한 다익스트라 알고리즘에서 영향을 받았으며, 경로 탐색 시 가장 기초적이면서 보편적으로 쓰이는 도구이다.

[EBS 제공, 가장 빠른길을 찾아라, 최단경로 알고리즘 시청각 자료]

2. 사용 예시

이 다익스트라 알고리즘은 가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용된다.

내비게이션처럼 두 도시를 잇는 가장 빠른 길을 찾는 문제
미로탐색 알고리즘
라우팅에서의 OSPF 방식의 프로토콜
공업입지론에서 최소 운송비 지점을 구할 때
루빅스 큐브를 푸는 프로그램 (A* 알고리즘)

3. 실행 과정

Start 정점을 설정한다. (그림 1 기준, 1번 또는 a)
Start를 기준으로 각 정점의 최소 비용을 저장한다.
방문하지 않은 정점 중 가장 비용이 적은 정점을 선택한다.
해당 정점을 거쳐서 특정한 정점으로 가는 경우를 고려해 최소 비용을 갱신한다.
3 ~ 4번 을 반복한다.

우선순위 큐를 사용해 현재 탐색 중인 정점과 그 거리를 저장하고, 거리가 짧은 순으로 처리한다.

dist 배열을 이용해 각 정점까지의 최단 거리를 저장하고, Start 정점의 거리는 0이고, 다른 정점은 무한대로 설정하고 시작한다. (초기화) 이후 우선순위 큐에서 하나씩 꺼내며 인접한 정점을 탐색하고, 거리에 따라 더 짧은 경로를 발견하면 갱신하는 방식으로 진행한다.

4. 소스 코드

data class Edge(val to: Int, val weight: Int)

fun dijkstra(V: Int, start: Int, graph: List<MutableList<Edge>>) {
    // 각 정점까지의 최단 거리를 저장할 배열 (무한대로 초기화)
    val dist = IntArray(V + 1) { Int.MAX_VALUE }
    dist[start] = 0  // 시작 정점의 거리는 0으로 초기화

    // 우선순위 큐 생성 (거리가 짧은 순서대로 정렬)
    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })
    pq.offer(Pair(start, 0))  // 시작 정점과 거리를 큐에 추가

    // 우선순위 큐가 빌 때까지 반복
    while (pq.isNotEmpty()) {
        val (current, currentDist) = pq.poll()

        // 큐에서 꺼낸 거리가 이미 기록된 거리보다 크면 무시
        if (currentDist > dist[current]) continue

        // 현재 정점에서 갈 수 있는 다른 정점들에 대해 거리 갱신
        for (edge in graph[current]) {
            val next = edge.to
            val nextDist = currentDist + edge.weight

            // 더 짧은 경로를 발견하면 거리 갱신 후 큐에 추가
            if (nextDist < dist[next]) {
                dist[next] = nextDist
                pq.offer(Pair(next, nextDist))
            }
        }
    }

    // 결과 출력: 각 정점까지의 최단 거리를 출력
    for (i in 1..V) {
        if (dist[i] == Int.MAX_VALUE) {
            println("INF")  // 경로가 없으면 INF 출력
        } else {
            println(dist[i])  // 경로가 있으면 최단 거리 출력
        }
    }
}

해당 소스 코드는 백준 1753번: 최단경로를 기준으로 작성되었다.

결과 출력이나 세세한 부분들은 문제에 따라 달라질 수 있다.

https://small-stepping.tistory.com/1190

1753번: 최단경로

문제 출처 : https://www.acmicpc.net/problem/1753 언어 : Kotlin 문제 설명 :방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단,

small-stepping.tistory.com