다익스트라 알고리즘 with Swift

알고리즘 문제를 풀다가 최단 경로에 관한 문제를 풀게 되었는데, 알고리즘에 대한 정확한 개념을 공부한 지 너무 오래된 것 같아 다시 공부해보았다! 최단 경로에 대한 알고리즘은 여러 가지가 있지만 이번엔 '다익스트라' 알고리즘에 대해 정리해보고자 한다.

 

다익스트라 알고리즘에 대해 설명하기 전 최단 경로에 대한 설명을 간단히 해보자면,

 

최단경로 란?

- 유향 가중치 그래프를 가정

- 경로란, 한 정점에서 다른 정점까지의 길을 의미

- 경로의 길이란, 경로를 구성하는 간선들의 가중치 합을 의미

- 최단 경로란, 시작정점 → 도착정점의 경로들 중 길이가 가장 작은 경로를 의미

 

이때, 최단 경로에 대한 것은 또 다음과 같이 구분할 수 있다.

- 단일 시작점 최단 경로 : 시작점 1개 → 모든 도착지

1. 가중치 값이 음이 아닌 경우 : 다익스트라

2. 가중치 값이 음을 허용하는 경우 : 벨만 포드

- 모든 쌍 최단 경로 : 모든 시작점 → 모든 도착지

 

 

다익스트라 알고리즘

- 프림 알고리즘과 유사

- 간선의 가중치가 모두 0 이상인 경우에만 가능

- 아래 6-1의 과정을 힙을 사용하여 구현한다면 O(ElogV)의 시간이 소요된다

 

기본 원리

1. 시작 노드로부터 연결된 노드들을 찾아 값을 업데이트하며

2. 연결된 노드들 중 최단 거리가 가장 짧은 노드를 골라 그와 연결된 노드들의 값을 업데이트한다.

이때 업데이트할 노드는 집합 S에 포함되어 있지 않아야 하며, 기존의 값보다 새로 업데이트 할 값이 더 작은 경우에만 업데이트한다.

3. 위 과정을 반복하여 수행하면 각 노드는 시작 노드로부터 최단 거리의 값을 갖게 된다.

 

알고리즘 개요

1. 그래프 그리기
2. 시작 위치로부터 각 정점까지의 최단 거리(비용)를 나타내는 배열을 초기화 (가장 큰 값)

3. 시작 위치의 비용은 0으로 초기화
4. 집합 S에 속하는지 여부를 나타내는 배열 초기화 (S 집합이 의미하는 것 : 최단거리 계산이 끝났다는 의미)
5. 우선순위 큐에 시작 위치 넣기

-- 이때, 우선순위 큐에 들어있다는 것이 의미하는 것은 집합 S에 포함되어 있지 않으면서 S와 연결된 정점들을 갖게 됨
6. 우선순위 큐에 노드가 있는 동안 반복
6-1. 우선순위 큐(힙)에서 최단거리가 가장 짧은 노드를 뽑기
6-2. 해당 노드를 S 집합에 추가
6-3. 해당 노드에 연결되어 있는 노드들의 비용을 업데이트
6-3-1. S에 포함되지 않으면서, 기존 비용보다 새로 업데이트할 비용이 더 작다면
6-3-2. 비용 업데이트 및 우선순위 큐에 추가

 

그림으로 이해하기!

1-3. 그림을 보면 시작 노드(1번)를 먼저 집합 S에 포함시키고 그와 연결된 노드들을 업데이트해줍니다. 따라서 연결된 노드인 2, 4, 5번 노드는 우선순위 큐에 추가됩니다.

4. 우선순위 큐 노드 중 가장 작은 값을 가진 2번 노드가 집합 S에 포함되며 그와 연결된 노드(3번)가 업데이트되고 큐에 추가됩니다.

5. 반복해서 우선순위 큐 노드 중 가장 작은 값을 가진 5번 노드가 pop 된 뒤 집합 S에 포함되고 그와 연결된 노드를 업데이트하는데, 2번 노드의 경우는 집합 S에 포함되어 있기 때문에 업데이트 대상이 되지 않으며 11번 노드는 기존 값이 더 작기 때문에 업데이트되지 않습니다. 따라서 3번 노드만 새로운 값으로 업데이트되고 큐에 추가됩니다.

 

이 과정을 반복하면 아래 이미지의 마지막 그래프의 모습과 같이 최종적으로 업데이트됩니다!

 

 

구현

var graph = Array(repeating: [(Int, Int)](), count: N+1)
// 1. 그래프 그리기

// 2. 시작 위치로부터 각 노드까지의 최단 거리를 나타내는 배열
var costs = Array(repeating: Int.max, count: N+1)

func dijkstra(start: Int) {

    // 3. 시작 위치는 0으로 초기화
    costs[start] = 0
    // 4. 집합 S 에 속하는지 여부를 나타내는 배열 (S 집합이 의미하는 것 : 최단거리 계산이 끝났다는 의미)
    var s = Array(repeating: false, count: N+1)

    // 5. 우선순위 큐에 시작 위치 넣기
    var heap = Heap<(Int, Int)((1, 0))
    // 6. 우선순위 큐에 노드가 있는 동안 반복
    while !heap.isEmpty {
        // 6-1. 가장 비용이 작은 노드 가져오기 (swift 에는 heap이 제공되지 않기 때문에 직접 구현해야함. 아래 코드는 임의 작성)
        let (node, cost) = heap.pop()
        // 6-2. S 집합에 추가
        s[town] = true
        // 6-3. 뽑힌 노드에 연결되어 있는 노드들의 비용을 업데이트
        for (next, value) in graph[node] {
            // 6-3-1. S에 포함되지 않으면서, 기존 비용보다 새로 업데이트할 비용이 더 작다면
            if !s[next], cost + value < costs[next] {
                // 6-3-2. 비용 업데이트 및 우선순위 큐에 추가
                costs[next] = value + time
                heap.push((next, costs[next]))
            }
        }
    }
}

// 시작 노드가 1인 경우
dijkstra(start: 1)

 

관련 문제

#	문제	풀이
1	[프로그래머스] 배달	🔗
2	[프로그래머스] 가장 먼 노드	🔗
3	[프로그래머스] 택시 합승 요금	🔗

 

 

음의 가중치가 있으면 안 되는 이유?

기본적으로 다익스트라 알고리즘은 다음 사항에 대한 것을 가정하고 진행한다.

→ 집합 S에 포함된 정점들에 대해서는 최단 거리의 계산이 완료되었다.

(집합 S에 포함된 정점들은 더 이상 최단 거리를 업데이트 하지 않는다)

→ 따라서 V-S에 있는 정점들의 거리 갱신이 올바르게 일어날 수 있다.

 

그렇다면 다음의 예를 보자.

 

5번 노드에서 2번 노드로 향하는 가중치를 -15로 변경해보았다.

앞 세번의 과정까지는 이전과 동일하게 발생하나 5번 노드에서 업데이트 할 때 문제가 발생한다.

 

1. 5번 노드에서 2번 노드로 향하는 가중치가 -15이고 이전 값보다 작아질 수 있기 때문에(8 → -6) 원래는 (2)번 그래프와 같이 업데이트 되는 것이 맞다. 하지만 2번 노드는 이미 집합 S에 포함되었기 때문에 (1)번 그래프와 같이 더이상 값이 업데이트 되지 않는다.

2. 만약 코드를 조금 바꿔서 2번 노드가 (2)번 그래프와 같이 변경되었다고 하자. 그렇지만 3번 노드 또한 값이 새로 업데이트 되어야 하는데 2번 노드는 집합 S에 포함되어 있으므로 이것과 연결된 노드를 업데이트 할 기회가 발생하지 않는다.

 

즉, 음의 가중치가 포함되면 이처럼 다익스트라 알고리즘이 전제로 하는 논리적 기반이 무너지기 때문에 올바르게 작동할 수 없다.