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

오늘은 다익스트라 알고리즘에 대해서 알아보자.

다익스트라 알고리즘

다익스트라 알고리즘은 하나의 node에서 다른 node로 가는 최단경로를 구하고 싶을때 사용한다.

즉, 시작접에서 다른 모든 정점까지의 최단 경로의 길이를 찾는 알고리즘이다.

---

조건

다익스트라 알고리즘을 사용할 수 있는 몇가지 조건이 있다.

• 방향 그래프를 가정으로 둔다.
  (무방향 그래프가 주어진다면 간선을 분리해서 방향 그래프로 바꿔야 한다.)
• 0 이상 가중치여야 한다.
  음수 가중치가 있으면 안된다.
  (이전까지 계산해둔 최소가 최소라고 보장할 수 없기 때문이다.)
• 사이클이 없어야 한다.

위와 같은 조건들을 모두 충족해야만 다익스트라 알고리즘을 사용할 수 있다.

다익스트라 알고리즘은 일종의 길찾기 알고리즘이다.
길찾기 알고리즘에는 다양한 종류가 있으므로 위와 같은 조건을 만족 하지 않을때에는 크루스칼이나 벨만 포드와 같은 알고리즘을 사용할 수 있다.
나중에 알아보도록 하자.

---

아이디어

다익스트라의 기본적인 아이디어를 살펴보자.

• BFS가 베이스이다.
  BFS처럼 시작 정점에서 가까운 순서대로 방문하게 된다.
• 그리디 알고리즘
  매 순간 최단 거리 정점을 선택하므로 그리디 알고리즘 기반이다.

다익스트라를 구현하는데 필요한 변수는 아래와 같다.

• int[] distance / var distance: [Int]
  각각의 노드까지의 최단 거리를 저장하는 배열
• boolean[] checked / var checked: [Bool]
  각각의 노드 방문을 체크하는 배열

---

그림으로 이해하기

시작점 A에서 최단거리를 구해보자.

1. distance와 checked 배열을 최대값으로 초기화한다.

distance에 최단 거리를 저장하기로 했으니 아무 곳도 방문하지 않은 초기에는 최대값으로 배열을 초기화한다.
(Integer.MAX_VALUE로 초기화하기도 하지만 최대 값이 10000이라면 10001로 초기화해도 된다.)

checked에 노드 방문을 체크하기로 했으니 아무 곳도 방문하지 않은 초기에는 false로 배열을 초기화 한다.

2. 시작점 A

A가 시작점이니 해당 노드 방문 거리는 0이다.
또한, 노드 방문을 체크하는 배열인 checked도 true로 변경한다.

3. A와 연결되어 있는 노드들의 distance를 갱신한다.

현재 노드인 A와 연결되어 있는 노드들은 B와 C이다.

3-1. B distance 갱신

3-2. C distance 갱신

4. 방문 가능한 정점 중 distance가 가장 작은 node를 찾아 방문한다.

B 노드의 distance가 2이므로 가장 작으므로 B 노드를 방문한다.

5. B와 연결되어 있는 노드들의 distance를 갱신한다.

현재 노드인 B와 연결되어 있는 노드들 중 방문 가능한 노드들의 distance를 갱신한다.
현재 B 노드에서는 C 노드를 방문할 수 있다.

❗️ 그런데 이미 C 노드의 distance가 정해져 있다.
우리는 위에서 distance 배열에 최단 거리를 저장하기로 정했다.

A -> B -> C의 총 거리는 3이다.
A -> C의 총 거리는 4이다.
그러므로 우리는 C 노드의 distance에는 3을 저장해야 한다.

위의 예제는 노드가 3개이지만 더 많은 노드에서라면 모든 노드를 방문할때까지 3~5번을 반복하면 된다.

---

코드로 보기

백준 1753: 최단경로 문제로 이해해보자.

struct EdgeData: Comparable {
    static func < (lhs: EdgeData, rhs: EdgeData) -> Bool {
        lhs.cost < rhs.cost
    }
    var cost: Int
    var node: Int
}

func solution() {
    let inf = Int.max
    let firstLine = readLine()!.split(separator: " ").map{ (subString) -> Int in
        return Int(String(subString))!
    }
    let v = firstLine[0]
    let e = firstLine[1]
    let start = Int(readLine()!)! - 1
    
    var graph = Array(repeating: [(Int, Int)](), count: v)
    for _ in 0..<e {
        let line = readLine()!.split(separator: " ").map( {Int(String($0))!} )
        graph[line[0] - 1].append((line[1] - 1, line[2]))
    }
    var d = Array(repeating: inf, count: v)
    d[start] = 0
    
    var pq: Heap = Heap<EdgeData>()
    pq.insert(EdgeData(cost: 0, node: start))
    while(!pq.isEmpty) {
        let now = pq.delete()!
        if d[now.node] < now.cost {
            continue
        }
        for next in graph[now.node] {
            if now.cost + next.1 < d[next.0] {
                d[next.0] = now.cost + next.1
                pq.insert(EdgeData(cost: now.cost + next.1, node: next.0))
            }
        }
    }
    for i in d {
        if i == inf {
            print("INF")
        } else {
            print(i)
        }
    }
}
solution()

• 그래프 연결선 데이터인 EdgeData를 정의했다.
• 최단거리를 확인해야하는 노드들을 우선순위큐를 통해 관리한다.

---

오늘은 다익스트라 알고리즘에 대해서 알아봤다.
다익스트라를 알아야만 풀리는 문제들이 있어서 이참에 정리해봤다.
나중에 다른 길찾기 알고리즘들도 다뤄봐야지 그럼 이만👋