최단 경로 문제

글 작성자: Coding Groot

최단 경로 문제는 그래프 내의 두 정점(노드) 간의 가장 짧은 경로, 즉, 각 간선들의 가중치의 합이 최소가 되는 경로를 찾는 문제이다.

그래프의 형태에 따라 다양한 최단 경로 알고리즘이 존재한다. 이러한 알고리즘은 그래프의 크기, 가중치의 존재 유무 또는 음수 사이클의 존재 여부 등에 따라 다르게 사용한다.

대표적인 알고리즘

복습할 겸 대표적인 최단 경로 알고리즘을 찾아봤다.

다익스트라 알고리즘: 가중치가 음수가 아닐 때 사용될 수 있다. 다익스트라가 대학원생이던 시절 여자 친구와 함께 커피숍에 갔다가 20분 만에 고안한 알고리즘으로도 유명하다.
벨만-포드 알고리즘: 음수인 가중치를 처리할 수 있는 알고리즘이다. 음수 사이클을 탐지할 수 있는 것이 특징이다.
플로이드-워셜 알고리즘: 가중치가 있는 그래프에서 모든 정점 쌍 사이의 최단 경로를 계산하는 DP 알고리즘다. 단일 소스가 아닌 모든 노드 쌍 간의 최단 거리가 필요할 때 유용하다. 양수 및 음수 가중치 간선을 처리할 수 있지만 음수 가중치 사이클은 처리할 수 없는 것이 특징이다.
A* 알고리즘: 휴리스틱 기반으로 최단 경로를 찾는 알고리즘이다. 낮은 비용으로 효과적인 경로 탐색을 수행할 수 있어서 게임 분야에서 자주 사용된다.
BFS: 가중치가 모두 1이면 BFS를 써도 된다.

이 중에서 가장 유명한 다익스트라 알고리즘을 살펴보자.

다익스트라 알고리즘

다음은 GitHub에서 가져온 다익스트라 알고리즘이다.

다익스트라 알고리즘의 아이디어는 간단하게 '탐욕적(greedy)' 접근 방식을 사용한다. (DP로도 분류하기도 한다.) 매 단계에서 가장 비용이 낮은 정점을 선택하고 그 정점을 통해 다른 정점으로 가는 경로를 탐색한다.

import heapq

def dijkstra(graph, start, end):
    """Return the cost of the shortest path between vertices start and end.

    >>> dijkstra(G, "E", "C")
    6
    >>> dijkstra(G2, "E", "F")
    3
    >>> dijkstra(G3, "E", "F")
    3
    """

    heap = [(0, start)]  # cost from start node, end node
    visited = set()
    while heap:
        (cost, u) = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        if u == end:
            return cost
        for v, c in graph[u]:
            if v in visited:
                continue
            next_item = cost + c
            heapq.heappush(heap, (next_item, v))
    return -1


G = {
    "A": [["B", 2], ["C", 5]],
    "B": [["A", 2], ["D", 3], ["E", 1], ["F", 1]],
    "C": [["A", 5], ["F", 3]],
    "D": [["B", 3]],
    "E": [["B", 4], ["F", 3]],
    "F": [["C", 3], ["E", 3]],
}
short_distance = dijkstra(G, "E", "C")
print(short_distance)  # E -- 3 --> F -- 3 --> C == 6

r"""
Layout of G2:

E -- 1 --> B -- 1 --> C -- 1 --> D -- 1 --> F
 \                                         /\
  \                                        ||
    ----------------- 3 --------------------
"""
G2 = {
    "B": [["C", 1]],
    "C": [["D", 1]],
    "D": [["F", 1]],
    "E": [["B", 1], ["F", 3]],
    "F": [],
}
short_distance = dijkstra(G2, "E", "F")
print(short_distance)  # E -- 3 --> F == 3

r"""
Layout of G3:

E -- 1 --> B -- 1 --> C -- 1 --> D -- 1 --> F
 \                                         /\
  \                                        ||
    -------- 2 ---------> G ------- 1 ------
"""
G3 = {
    "B": [["C", 1]],
    "C": [["D", 1]],
    "D": [["F", 1]],
    "E": [["B", 1], ["G", 2]],
    "F": [],
    "G": [["F", 1]],
}
short_distance = dijkstra(G3, "E", "F")
print(short_distance)  # E -- 2 --> G -- 1 --> F == 3

이 코드에서는 최단 경로를 탐색하는 과정을 효율적으로 하기 위해 min-heap을 사용했다.

[참고]
min-heap은 가장 작은 값을 root로 가지며, 이를 통해 매번 가장 낮은 비용을 가진 값을 O(1)으로 확인할 수 있다.
min-heap을 사용하면 가장 작은 인접 노드를 찾는 작업을 log(n)으로 수행할 수 있다.

코드에서 min-heap은 이전 정점과 현재 정점 사이의 거리뿐만 아니라 시작점에서 목표점까지의 경로를 구성하는 정점들 사이의 모든 거리를 저장한다. 따라서, heapq.heappop은 항상 최단 거리인 다음 정점을 반환하게 되고 min-heap으로 정점이 이미 탐색된 경우 최단 거리를 가진 다른 경로가 없다는 것을 보장받을 수 있다.

코드 설명

heap은 시작 정점에서 각 정점까지의 비용을 저장하는 min-heap이다. 초기에는 시작 정점만이 (0의 비용으로) 포함한다.

visited 집합은 이미 방문한 정점들을 추적한다.

while문으로 heap에 요소가 남아 있는 동안 계속 반복하며 가장 낮은 비용의 정점을 꺼낸다.

이미 방문한 정점이면 무시하고, 아니면 방문 처리한다.
목표 정점에 도달하면 현재까지의 비용을 반환한다.
현재 정점에서 인접한 모든 정점을 순회하면서, 각 정점까지의 총 비용을 계산하고 이를 힙에 추가한다

참고

최단 경로 문제 풀이: https://www.notion.so/coding-groot/abd27dbf306240d281a6a806d258eda3

다익스트라 코드 출처: https://github.com/TheAlgorithms/Python/blob/master/graphs/dijkstra.py

최단 경로 문제 - 다익스트라 알고리즘