[알고리즘] 최단경로 구하기 - 다익스트라, 벨만-포드 알고리즘 (백준 1916, 11657)

최단경로 구하기

가중치가 주어진 그래프에서 최단거리를 구할 때

가중치가 양수이고, 사이클이 존재하지 않을 경우 다익스트라

가중치가 음수를 포함하고, 사이클이 존재할 경우 벨만-포드 

알고리즘을 사용할 수 있다.

 

 

다익스트라 알고리즘

1. 시작노드를 설정하고 그 노드와 연결되어 있는 모든 노드들의 최단거리 테이블 갱신
2. 그 연결된 정점중에 비용이 최소인 노드 선택
3. 해당 노드에서 연결되어 있는 모든 노드들의 최단거리 테이블 갱신
4. 2,3 번 반복

다익스트라 알고리즘에서는 항상 비용이 최소인 노드를 선택하기 때문에

그리디 알고리즘의 성격을 띈다. 따라서 1,2번 과정에서 선택된 노드의 최단거리 테이블은 변하지 않기 때문에 사이클이 존재하거나, 가중치가 음수일 경우 사용이 불가능하다.

 

하지만 항상 최선의 경우를 탐색하기 때문에

O(VlogV) ( V : 정점 )

의 시간복잡도를 갖는다.

예제 코드 (백준 1916)

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

1916번: 최소비용 구하기

// [백준] 1916. 최소비용 구하기 (Kotlin)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

lateinit var dist: Array<Int>
lateinit var map: Array<ArrayList<Node>>

data class Node(val des: Int, val value: Int) : Comparable<Node> {
    override fun compareTo(other: Node): Int = value - other.value
}

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val n = readLine().toInt()
    val m = readLine().toInt()
    dist = Array(n + 1){Int.MAX_VALUE}
    map = Array(n + 1) {arrayListOf()}

    // 그래프 생성
    for(i in 0 until m){
        val st = StringTokenizer(readLine())
        val start = st.nextToken().toInt()
        val des = st.nextToken().toInt()
        val value = st.nextToken().toInt()

        map[start].add(Node(des,value)) // start에서 des로 가는 가중치 value
    }

    val st = StringTokenizer(readLine())
    val start = st.nextToken().toInt()
    val des = st.nextToken().toInt()

    dijkstra(start) // 시작점에서부터 탐색 시작
    println(dist[des]) // 목적지 최솟값 출력
}

fun dijkstra(srt: Int){
    val queue = PriorityQueue<Node>()

    dist[srt] = 0 // 시작점 자신은 0
    queue.add(Node(srt,0)) // 시작점 넣기

    while(queue.isNotEmpty()){
        val curIndex = queue.peek().des  // 현재 노드 인덱스
        val curValue = queue.peek().value  // 현재 노드까지의 거리
        queue.poll()

        if (dist[curIndex] < curValue) continue // 가중치가 더 큰 경로 탐색 X

        // 인접리스트 탐색
        for (i in map[curIndex]) {
            val nextDes = i.des
            val nextValue = curValue + i.value

            // 최솟값 갱신
            if (nextValue < dist[nextDes]) {
                dist[nextDes] = nextValue
                queue.add(Node(nextDes, nextValue))
            }
        }
    }
}

 

 

벨만-포드 알고리즘

1. 모든 간선을 탐색하여 최단거리 테이블 갱신
2. 1번 과정을 (정점의 수 - 1) 만큼 반복
3. 1번 과정을 한번 더 수행했을 때 최단거리 테이블이 갱신될 경우 싸이클 발생 확인

 

정점의 수를 n이라 할 때, 사이클이 존재하지 않는다면 최단 거리는 n-1 이다.

벨만-포드 알고리즘은 위 성질을 활용하여, 사이클이 발생하는지 찾는다.

 

사이클이 없을 때, 모든 간선을 n-1 만큼 반복 탐색하면 모든 최단거리 테이블이 완성된다.

그 후 한번 더 탐색했을 때 최단거리 테이블이 갱신된다면, 음수의 사이클이 존재하는 것이다.

 

하지만 모든 간선을 반복하여 탐색해야 하기 때문에

O(VE) ( V : 정점, E : 간선 )

의 시간복잡도를 갖는다.

예시 코드 (백준 11657)

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

11657번: 타임머신

// [백준] 11657. 타임머신 (Kotlin)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

lateinit var dist: Array<Long>
lateinit var adj: ArrayList<Node>
var n = 0
var m = 0
var cycle = false

data class Node(val start: Int, val des: Int, val value: Long)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val st = StringTokenizer(readLine())
    n = st.nextToken().toInt()
    m = st.nextToken().toInt()
    dist = Array(n + 1){Long.MAX_VALUE} // 최솟값 저장
    adj = arrayListOf() // 간선 정보 저장

    // 간선 정보 입력
    for(i in 0 until m){
        val st = StringTokenizer(readLine())
        val start = st.nextToken().toInt()
        val des = st.nextToken().toInt()
        val value = st.nextToken().toLong()

        adj.add(Node(start,des,value))
    }

    bellmanFord(1)

    // 사이클이 존재하면
    if (cycle){
        println("-1")
    }
    // 사이클이 존재하지 않으면
    else{
        for(i in 2 .. n){
            // 경로가 없다면
            if(dist[i] == Long.MAX_VALUE) {
                dist[i] = -1
            }
            println(dist[i])
        }
    }
}

fun bellmanFord(srt: Int){

    dist[srt] = 0 // 시작점 자신은 0

    for(i in 1 .. n){
        for(cur in adj){
            val curStart = cur.start
            val curDes = cur.des
            val nextValue = dist[curStart] + cur.value

            // 현재값이 초기화 된 상태이고 최솟값을 갱신할 수 있으면
            if(dist[curStart] != Long.MAX_VALUE && dist[curDes] > nextValue){
                dist[curDes] = nextValue

                // n번째 반복 때 최솟값이 갱신되었다면
                if(i == n){
                    cycle = true
                }
            }
        }
    }
}