다익스트라 알고리즘

#

다익스트라 알고리즘은 가장 대표적인 그래프 알고리즘 중 하나다.

"한 vertex 기준점에서 모든 vertex에 대한 최단거리를 빠르게 구하는" 알고리즘이다.



시간복잡도

이것도 처음부터 완성형으로 나온건 아니고, 여러차례 개량을 거쳐서 여러가지 형태가 있다.

초기 형태의 경우에는 O(N^2)의 시간복잡도를 가졌다. (여기서 N은 vertex의 개수다.)



응용

다익스트라 알고리즘은 생각보다 다양하게 활용되는 기반 알고리즘이다.
최소한의 비용으로 해답을 찾는 것에 최적화되어있고. 그래서 네비게이션에서의 길찾기라든가, 퍼즐 풀기라든가 하는 그런 것들에 응용되곤 한다.



원리

아이디어 자체는 동적 계획법(dynamic programming)을 주로 활용한다.

  1. 시작점을 기준으로 해서 모든 vertex과의 거리를 초기화한다. 각 vertex의 초기값은 무한대나, 해당 타입의 최댓값으로 둔다. 이 초기화의 대상은 버킷이라고 가칭하겠다.

  2. 시작점을 기준으로 해서, 바로 옆에 붙여있는 이웃 vertex들과의 거리를 계산한다. 그럼 바로 옆에 있던 vertex들에 한해서는 버킷 값이 거리값이 무한대가 아닌, 실제 숫자값으로 갱신될 것이다.

  3. 이웃 vertex에서 끝나면 안된다. 거기서 또 이웃의 이웃 vertex와의 거리를 계산한다.

  4. 그 이웃의 이웃 vertex가 원래 무한대였다면 버킷에서 유효한 그 거리 값으로 수정한다.

  5. 만약 이전 거리값과 총합했을때 지금 접근 경로가 총 거리가 더 짧다면, 이미 버킷에 유효한 값이 있었더라도 값을 갱신한다.





대략적으로 이러한 과정을 반복해서 최단거리를 찾아나간다고 보면 된다.
다만 여기서 성능 병목이 생길 수 있는 부분은 이전까지의 vertex를 순회하면서 총 거리가 가장 짧은 것을 판단하는 것인데, 여기에 무슨 구조를 사용하는지에 따라서 성능이 달라진다.

심플한 구현에서는 그냥 배열로 쓰기도 하는데, 그럼 데이터 사이즈에 따라 속도가 매우 느려질 수 있고, 이보다 나은 방법은 이진 힙으로 우선순위 큐를 관리하는 것이다. 그리고 가장 빠르다고 할 수 있는 방법은 피보나치 힙을 쓰는 것이다.

한번 코드를 직접 작성해보면서 그 원리를 이해해보겠다.
내 경우에는 이진 힙을 우선순위 큐로 사용하는 조금은 변형된 알고리즘을 구현했다.


그래프는 이런 구조로 잡았고


간선을 추가하는 유틸 함수다.

그리고 이런 형태로 그래프를 잡았다.

그림으로 그리면 이런 형태가 된다.




예제 코드: 이진 힙 기반의 변형 알고리즘 (Rust)

아래는 Rust로 작성한 이진힙 기반의 다익스트라 코드다.
Infinity 초기화같은건 따로 안한다. 배열로 잡지도 않고 맵으로 깔았기 때문이다.

// dijkstra 알고리즘
// graph: 전체 그래프
// start: 시작점
// return: 시작점으로부터 각 정점까지의 최단거리 맵
pub fn dijkstra<V: Ord + Copy + Debug, E: Ord + Copy + Debug + Add<Output = E>>(
    graph: &Graph<V, E>,
    start: V,
) -> BTreeMap<V, Option<(V, E)>> {
    let mut result_map = BTreeMap::new();
    let mut priority_queue = BinaryHeap::new();

    // 1. 시작지 초기화
    result_map.insert(start, None);

    // 2. 시작점을 기준으로 쭉 돌면서 시작지에서 갈 수 있는 vertex들을 다 map과 우선순위 큐에 넣음
    for (new, weight) in &graph[&start] {
        result_map.insert(*new, Some((start, *weight)));

        // 2.1. 가중치가 적은 것부터 꺼낼 수 있게 최소 힙에 넣음
        priority_queue.push(Reverse((*weight, *new, start)));
    }

    // 3. 우선순위 큐에서 하나씩 뽑아서
    while let Some(Reverse((dist_new, new, prev))) = priority_queue.pop() {
        // 3.1. 이미 result_map의 타겟으로 설정되어있던 vertex만 그대로 진행
        match result_map[&new] {
            Some((v, e)) if v == prev && e == dist_new => {}
            _ => continue,
        }

        // 3.2. 인접 노드들에 대해 최단거리를 계산
        for (next, weight) in &graph[&new] {
            match result_map.get(next) {
                // 3.2.1. 새로 계산된 최단거리가 기존의 최단거리보다 크다면 무시하고 버림
                Some(Some((_, dist_next))) if dist_new + *weight >= *dist_next => {}
                // 3.2.2. 아직 방문하지 않은 노드도 무시하고 버림
                Some(None) => {}
                // 3.2.3. 새로 나온 최단거리를 넣고 우선순위 큐에도 추가
                _ => {
                    result_map.insert(*next, Some((new, *weight + dist_new)));
                    priority_queue.push(Reverse((*weight + dist_new, *next, new)));
                }
            }
        }
    }

    // 4. 결과 반환
    result_map
}

하나씩 풀어보겠다.


함수 자체는 그래프와 시작점을 인자로 받고, 그 시작점에 대한 각 vertex의 최단거리 쌍을 반환한다.


우선 기본 맵과 힙을 생성하고, 시작점을 초기화한다.
시작점에서 시작점으로 가는건 의미가 없으니까 저렇게만 넣어둔다.


그리고 시작점을 기준으로 해서 그 이웃 vertex에 대해서만 일괄적으로 결과 맵과 이진힙에 넣고 시작한다.

자

그럼 여기서부터 방금 넣어둔 이진힙을 기반으로 뺑뺑이를 돌기 시작한다.
A를 시작점으로 잡았다면 아마 가장 가까운 B부터 나왔을 것이다.


그럼 그 B에 대해서도 재귀적으로 인접 노드들을 다시 접근한다.
여기서 이제 조건을 다 거르고 합산된 거리가 가장 짧다면 result_map과 이진힙에 다시 넣어서 모든 것을 다 돌아서 처리할때까지 계속해서 순환한다.


힙에 들어있는걸 다 꺼내썼다면 반환하고 종료한다.


한번 a를 기준으로 한 최단거리를 뽑아보자


그러면 이렇게 기대한대로 가져올 것이다.
b는 바로 거리 10으로 바로 이어지니까 10이고, c는 A->D->C로 경로 20이 잘 나왔다.

전체 코드다.

use std::cmp::Reverse;
use std::collections::{BTreeMap, BinaryHeap};
use std::fmt::Debug;
use std::ops::Add;

// 그래프 타입
// V: Vertex 타입
// E: 가중치 타입
type Graph<V, E> = BTreeMap<V, BTreeMap<V, E>>;

// dijkstra 알고리즘
// graph: 전체 그래프
// start: 시작점
// return: 시작점으로부터 각 정점까지의 최단거리 맵
pub fn dijkstra<V: Ord + Copy + Debug, E: Ord + Copy + Debug + Add<Output = E>>(
    graph: &Graph<V, E>,
    start: V,
) -> BTreeMap<V, Option<(V, E)>> {
    let mut result_map = BTreeMap::new();
    let mut priority_queue = BinaryHeap::new();

    // 1. 시작지 초기화
    result_map.insert(start, None);

    // 2. 시작점을 기준으로 쭉 돌면서 시작지에서 갈 수 있는 vertex들을 다 map과 우선순위 큐에 넣음
    for (new, weight) in &graph[&start] {
        result_map.insert(*new, Some((start, *weight)));

        // 2.1. 가중치가 적은 것부터 꺼낼 수 있게 최소 힙에 넣음
        priority_queue.push(Reverse((*weight, *new, start)));
    }

    // 3. 우선순위 큐에서 하나씩 뽑아서
    while let Some(Reverse((dist_new, new, prev))) = priority_queue.pop() {
        // 3.1. 이미 result_map의 타겟으로 설정되어있던 vertex만 그대로 진행
        match result_map[&new] {
            Some((v, e)) if v == prev && e == dist_new => {}
            _ => continue,
        }

        // 3.2. 인접 노드들에 대해 최단거리를 계산
        for (next, weight) in &graph[&new] {
            match result_map.get(next) {
                // 3.2.1. 새로 계산된 최단거리가 기존의 최단거리보다 크다면 무시하고 버림
                Some(Some((_, dist_next))) if dist_new + *weight >= *dist_next => {}
                // 3.2.2. 아직 방문하지 않은 노드도 무시하고 버림
                Some(None) => {}
                // 3.2.3. 새로 나온 최단거리를 넣고 우선순위 큐에도 추가
                _ => {
                    result_map.insert(*next, Some((new, *weight + dist_new)));
                    priority_queue.push(Reverse((*weight + dist_new, *next, new)));
                }
            }
        }
    }

    // 4. 결과 반환
    result_map
}

fn add_edge<V: Ord + Copy, E: Ord>(graph: &mut Graph<V, E>, v1: V, v2: V, c: E) {
    graph.entry(v1).or_default().insert(v2, c);
    graph.entry(v2).or_default();
}

fn main() {
    let mut graph = BTreeMap::new();
    add_edge(&mut graph, 'a', 'b', 10);
    add_edge(&mut graph, 'a', 'c', 30);
    add_edge(&mut graph, 'a', 'd', 15);
    add_edge(&mut graph, 'b', 'e', 20);
    add_edge(&mut graph, 'e', 'f', 20);
    add_edge(&mut graph, 'c', 'f', 5);
    add_edge(&mut graph, 'd', 'c', 5);
    add_edge(&mut graph, 'd', 'f', 20);
    add_edge(&mut graph, 'f', 'd', 20);

    let result = dijkstra(&graph, 'a');
    println!("{:?}", result);
}

참조
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
https://github.com/TheAlgorithms/Rust/blob/master/src/graph/dijkstra.rs