[DIscrete Mathematics] 다익스트라 알고리즘(Dijkstra algorithm)

---

최단 경로 문제 (Shortest Path Problem)

 

가중치 그래프는 간선에 값을 부여한 그래프이다. 이때 경로의 길이는 경로 안의 간선의 가중치 합으로 정의하고, 간선 $ (i, j) $ 의 가중치를 $ w (i, j) $ 라 표기한다.

가중치 그래프가 있을 때 2개의 정점 간 가장 길이가 짧은 경로를 찾는 최단 경로 문제는 내비게이션, 통신망 등 여러 분야에서 활용된다.

 

---

다익스트라 알고리즘

 

다익스트라 알고리즘은 에츠허르 다익스트라가 고안한 최단 경로를 구하는 알고리즘이다. $ n $ 개의 정점으로 구성되고, 단순하며, 연결된 가중치 그래프에 대하여 최악의 경우 $ \mathcal{\Theta} (n^2) $ 의 시간복잡도를 가진다.

이 알고리즘은 가중치 그래프의 어느 한 정점에서 다른 정점으로의 최단 경로의 길이를 찾는 것이다.

입력: $ G $ (단순하며 연결된 가중치 그래프), $ w $ (가중치), $ a $ (시작 정점), $ z $ (도착 정점)
출력: $ L(z) $ ($ a $ 에서 $ z $ 까지의 최단 경로의 길이)

Dijkstra(G, w, a, z) {
    L[a] = 0
    T = [] // T는 a로부터 최단거리 계산이 안된 정점의 집합
    for each vertex v in G {
        if (v != a) {
            L[v] = INFINITY
            T = T + v
        }
    }
    while (T is not empty) {
        v = vertex in T with min L[v]
        T = T - v
        for each x in T adjacent to v {
            L[x] = min(L[x], L[v] + w(v, x))
        }
    }
    return L[z]
}

말로 풀어 설명하자면 먼저 출발점부터의 거리를 저장한 리스트를 초기화하고, 출발점으로부터 최단거리 계산이 안된 정점의 집합을 추가한다. 그 후 현재 최단 거리가 가장 짧은 정점을 선택한다. 선택된 정점은 최단거리 계산 안된 집합에서 제거한다. 그 후 선택된 정점과 선택한 정점에 인접한 정점들에 대해 인접한 정점을 거쳐가는 것이 빠른지 느린지를 계산하여 출발점으로부터 최단거리를 계산한다. 이를 반복하면 최종적으로 도착점에 대한 최단거리가 계산된다.