빽 투더 기본기 [알고&자구 5편]. 다익스트라 알고리즘

취업과 기본기 튼튼/빽 투더 기본기

빽 투더 기본기 [알고&자구 5편]. 다익스트라 알고리즘

흠시 2019. 4. 19. 20:58

그래프에서 경로찾는 알고리즘 중, 가장 유명한 다익스트라(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)가 음수인 경우에는 어떻게 해야할까?

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

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

[2020.7.2 수정]

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

저작자표시