최단거리 알고리즘 - 다익스트라(dijkstra) feat.kotlin

 다익스트라(dijkstra) 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. 

 

"특정" 노드에서 다른 "모든"노드로 가는 최단경로를 계산한다.

 양의 가중치에서 사용한다.

 

매 상황(현재 노드에서 다른 노드로 이동)때 가장 비용이 적은 노드를 선택한다(그리디)

현재 최소거리 Distance Table을 갱신하면서, dp 유형에도 해당하는 알고리즘이다.

 

예시) 아래와 같은 무방향 그래프가 주어졌다고 가정하자.

 

출발점 A로 시작한다 가정하면, 갈수 있는곳은 B, D 두 군데이며,테이블을 갱신 후,  시작점(A)에서 가까운 B로 간다.

 

 

B로 이동후, 갈수 있는곳은 E, D 두 군데이며, 테이블을 갱신 후, 시작점(A)에서 가까운 D로 간다.

 

 

D로 이동후, 갈수 있는곳은 E, F 세 군데이며, (단 B는 재방문하면 안됨) 테이블을 갱신 후, 시작점(A)에서 가까운 E로 간다.

 

E로 이동후, 갈수 있는곳은 D F 두 곳이며, (단 B,D는 재방문하면 안됨) 테이블을 갱신 후, 시작점(A)에서 가까운 F로 간다.

 

F로 이동후, 갈수 있는곳은 D F 두 곳이며, (단 B,D는 재방문하면 안됨) 테이블을 갱신 후, 시작점(A)에서 가까운 C로 간다.

 

더 이상 방문할 노드가 존재하지 않으며 테이블 또한 갱신되지 않는다.

 

 

실질적인 문제를 해결하는 논리적 순서.

 

1. 출발 노드를 정한다.
2. 최단거리 테이블(Array 등) INF 초기화 한다.
3. "방문하지 않은 노드"중에서 최단거리(비용)이 가장 짧은 노드를 선택한다. --> 

- 이때, 선택된 노드로 가는 최단거리는 추후 절대 변경이 안된다 (양의 가중치 라면).
4. 3번에서 선택한 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신합니다.

* "방문하지 않은 노드중"에 최단 거리 가장 짧은 노드를 선택할 때 PriorityQueue 사용한다.

- 가장 짧은 노드를 선택할 때, 단순 반복문을 사용해도 되지만, 시간 효율성 측면에서 좋지 않다.

 

구현 코드

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

import java.util.PriorityQueue

var n = 0
var m = 0

// 가중치를 가진 인접리스트
lateinit var adjList: Array<MutableList<Pair<Int, Int>>>

val INF = 1_000_000_000
lateinit var dist: Array<Int>

fun dijkstra(start: Int) {
	
    // 가중치를 적은것을 우선순위로 두는 PQ
    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.second })
	
    // 시작점 갱신 및 삽입.
    dist[start] = 0
    pq.add(start to 0)

    while (pq.isNotEmpty()) {
        // 현재 노드에서 가장 적은 비용으로 지날수 있는 간선 선택.
        val edge = pq.poll()
        val u = edge.first

        // 이미 방문되어 최소값이 정해진 노드 건너뜀(visted가 없어도됨)
        if (dist[u] < edge.second)
            continue
		
        // 갱신하고, 다음 갱신을 위해 pq에 넣음.
        for (next in adjList[u]) {
            val v = next.first
            val w = next.second
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w
                pq.add(v to dist[v])
            }
        }
    }
}

fun main() = with(System.`in`.bufferedReader()) {

    n = readLine().toInt()
    m = readLine().toInt()

    adjList = Array(n + 1) { mutableListOf() }

    for (i in 1..m) {
        val edge = readLine().split(" ").map { it.toInt() }
        val u = edge[0]
        val v = edge[1]
        val w = edge[2]

        adjList[u].add(v to w)
    }

    dist = Array(n + 1) { INF }

    val info = readLine().split(" ").map { it.toInt() }
    dijkstra(info[0])
    println(dist[info[1]])
}