빽 투더 기본기 [알고&자구 5편]. 다익스트라 알고리즘

그래프에서 경로찾는 알고리즘 중, 가장 유명한 다익스트라(Dijkstra) 알고리즘을 잠깐 정리해볼까 한다.

글 대부분의 내용은 Chancethecoder님 블로그 와 허민석님 유튜브를 참고하였다.

한 점에서 다른 정점으로 가는 최단 경로 찾기

위 제목이, 다익스트라 알고리즘이 하는 일이다.
방향 혹은 무방향 그래프에서, 어떤 한 점에서, 다른 모든 점으로 가는 최단 경로와 거리(weight) 을 O(|V||E|) 만에 찾아서 반환한다.

이 때, 거리(weight) 는 모두 양수여야 알고리즘이 제대로 작동한다.
또, 정점(vertex)과, 인접 행렬(adjacent)이 입력으로 주어져야 한다.

알고리즘

알고리즘을 간단하게 정리하면 다음과 같다.

1. 시작점에서 모든 정점까지의 거리를 담는 배열 (dist) 를 만든다.
2. dist에 시작점을 제외하고, 모두 무한대(inf) 로 설정한다.
3. (시작점, 현재 정점까지의 거리) 을 최소힙에 넣는다. 시작점의 경우 거리는 0이다.
4. 최소힙에서 하나의 정점을 pop한다.
5. 이 정점과 연결된 인접 정점을 adjacent 로 찾는다.
6. (현재 정점까지의 거리 + 현재 정점에서 인접 정점까지의 거리) 와 dist[인접 정점] 거리를 비교하여, 왼쪽이 작을 경우, dist[인접 정점]을 이 값으로 업데이트 한다.
7. 최소힙에 (인접 정점, 인접 정점까지의 거리)를 넣는다.
8. 최소힙이 빌 때까지 4를 반복한다.

글로 쓰니 복잡해보이는데... 그냥 위에 링크해놓은 허민석님 유튜브를 보면 8분만에 이해할 수 있다.

어디가서, 한마디로 설명하라 하면 다음과 같이 말하면 된다.

다익스트라 알고리즘은 정점을 하나씩 추가하면서 그 때 최적값을 찾아 Relax(더 낮은 거리로 업데이트) 하는 구조다.

코드

정점과 인접 행렬이 먼저 입력으로 주어저야 한다고 했다.
다음과 같은 그래프의 상황이라고 할 때, 이를 파이썬식으로 표현하면 다음과 같다.

출처 : 허민석님 유튜브

v = list("ABCDEF")
adjacent = {
    "A": {
        "B": 3,
        "C": 2,
        "D": 4,
    },
    "B": {
        "A": 3,
        "D": 2,
        "F": 5
    },
    "C": {
        "A": 2,
        "E": 1
    },
    "D": {
        "A": 4,
        "B": 2,
        "E": 1,
        "F": 3
    },
    "E": {
        "C": 1,
        "D": 1,
        "F": 2,
    },
    "F": {
        "B": 5,
        "D": 3,
        "E": 2
    }
}

이제 다익스트라 알고리즘을 코드로 표현하면 다음과 같다.
시작점 start는 'A' 로 두었다.

def dijkstra(start, adjacent):
    min_heap = []
    prev = { v: -1 for v in adjacent.keys()}
    dist = { v: float('inf') for v in adjacent.keys() }

    heapq.heappush(min_heap, (0, start))
    dist[start] = 0

    while min_heap:
        current_dist, current_v = heapq.heappop(min_heap)

        for next_v, next_dist in adjacent[current_v].items():
            total_dist = current_dist + next_dist

            if total_dist < dist[next_v]:
                dist[next_v] = total_dist
                prev[next_v] = current_v
                heapq.heappush(min_heap, (total_dist, next_v))

    return dist, prev


start = 'A'
dist, prev = dijkstra(start, adjacent)

for v, dist in dist.items():
    print("%s -> %s : %s" %(start, v, dist) if dist != float('inf') else "INF")

이를 출력하면 다음과 같이 A에서 다른 정점으로 가는 최단거리가 나온다.

# output
A -> A : 0
A -> B : 3
A -> C : 2
A -> D : 4
A -> E : 3
A -> F : 5

거리(Weight)가 음수인 경우에는 어떻게 해야할까?

다익스트라는 거리가 양수인 경우에만 적용가능하다고 했다. 그럼 음수일 때는 어떻게 해야할까?
이에 대한 답은 생각보다 간단한데, 다음과 같다.

1. 모든 거리에 어떤 수를 더해주어, 모두 양수로 만들어 준 뒤,
2. 알고리즘을 돌린다.
3. 나온 결과값을 다시 어떤 수를 빼준다.

[2020.7.2 수정]

거리가 음수일 때, 걍 weight + @alpha 해서 모두 양수로 만들어버리면 되잖아? 라고 왜 생각했었지??
아마도 ratsgo님 블로그 글을 보고 그런 생각을 했던 듯 하다.
물론 모두 양수로 만들면 그럴듯하게 되어 보이지만, 다익스트라는 출발점을 시작으로 근시안 적인 탐색을 하며 greedy 하게 가기 때문에, 가중치가 감소하는 것을 고려 못한다. 가장 직관적으로 설명된 글은 여기에 있다.