9. 최단 경로

Intro

가장 짧은 경로를 찾는 알고리즘, 최단 경로(Shortest Path) 알고리즘은 많은 길 찾기 문제에 필요하다. 

이 알고리즘 유형에도 다양한 종류가 있고, 다행히 각 상황(한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우, 단순히 최단 거리를 출력해야 하는 경우 등)에 맞는 효율적인 알고리즘들이 이미 정립되어 있다고 하니 학습해보자.

 

최단 경로 문제는 보통 그래프를 이용해 표현한다. 그래프에서 각 지점은 정점(vertex) 또는 노드(node)로 표현되고, 지점간 연결된 도로는 간선(edge)으로 표현된다. 

그래프

대표적인 최단 거리 알고리즘에는 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘이 있는데 코딩 테스트에서 가장 많이 등장한다는 앞의 두 유형을 공부해보자. 

* 앞서 공부한 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용된다. . .〒▽〒

 

 

 

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

Dijkstra 최단 경로 알고리즘은 특정한 노드에서 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 이 알고리즘은 '음의 간선'이 없을 때 정상적으로 동작한다. (～￣▽￣)～ 현실 세계의 길이 0보다 작은 값을 가지는 간선으로 표현되지 않으므로 이 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다.

이 알고리즘은 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복한다. 그렇기에 현재 상황에서 지금 당장 좋은 것만 고르는 방법인 그리디 알고리즘(매 순간 가장 좋아보이는 것을 선택, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않기)으로 분류된다. 

 

   𝟙  출발 노드 설정하기

   𝟚  최단 거리 테이블 초기화하기

   𝟛  방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택하기

   𝟜  해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신하기

   𝟝  𝟛~𝟜번 반복하기  

 

이렇게 최단 경로를 구하는 과정에서 각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트(최단 거리 테이블)에 저장하며 리스트를 계속 갱신하는 방법이다. 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인하면서, 나중에 현재 처리하고 있는 노드와 인접한 노드로 도달하는 더 짧은 경로를 찾으면 그 경로로 업데이트하는 것이다. (저번에 풀었던 미로탈출이나 백준 토마토문제 방식인듯하다)

 

모든 노드를 방문할 때까지 최단 거리 테이블을 갱신한다.

 

이제 이 알고리즘을 구현하면 되는데. . . 방법은 두 가지이다. +_+

 

방법 1) 간단한 다익스트라 알고리즘

구현하기 쉽지만 느리게 동작하는 코드이다. 먼저 1차원 리스트를 선언하면, 이 리스트를 채우고 갱신하는 과정을 통해 최종적으로 각 노드에 대한 최단 거리를 담게 된다. 그 과정에서는 단계마다 '방문하지 않은 노드' 중에서 '최단 거리가 가장 짧은 노드'를 선택하기 위해 매번 1차원 리스트의 모든 원소를 순차적으로 탐색한다.

 

Dijkstra_simple.py

# 간단한 다익스트라 알고리즘

# 입력
# 6 11
# 1
# a b c -> a에서 b로 가는 비용이 c


# 방문하지 않은 노드 중에서, 최단 거리가 가장 짧은 노드의 번호를 반환
def get_smallest_node():
    min_value = INF
    index = 0
    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index


# 다익스트라 알고리즘으로 최단 거리 테이블 채우기
def dijkstra(start):
    distance[start] = 0
    visited[start] = True

    # 시작 노드와 연결된 노드들에 대해서 거리 기록
    for j in graph[start]:
        distance[j[0]] = j[1]

    # 시작 노드를 제외한 모든 노드들에 대해 반복
    for i in range(n-1):
        now = get_smallest_node()
        visited[now] = True
        # now랑 연결된 n번째 노드들에 대해서
        for j in graph[now]:
            cost = distance[now] + j[1]
            # 시작 노드에서 now를 거쳐서 n번째 노드로 가는 비용이 기존 저장값보다 더 작으면
            if cost < distance[j[0]]:
                distance[j[0]] = cost   # 갱신

 

총 $O(V)$번에 걸쳐 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 하며, 현재 노드와 연결된 노드를 매번 일일이 확인하기에 이 알고리즘의 시간복잡도는 $O(V^2)$이다.

최단 경로 문제에서 전체 노드의 개수가 5,000개 이하라면 일반적으로 이 코드로 풀릴 것이다. 하지만 노드의 개수가 10,000개를 넘어가는 경우를 위해 더 빠른 알고리즘이 필요하다. 

---

방법 2) 개선된 다익스트라 알고리즘

이건 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드이다. 우리는 이 방법 2를 정확히 이해하고 구현할 수 있을 때까지 연습해야 한다. 

그러니까 다익스트라와 동작하는 기본 원리는 동일하지만 "현시점에서 방문하지 않은 노드 중에서 최단거리인 노드를 찾는 시간"만 줄인다는 아이디어이고, 힙 자료구조를 사용해 이를 실현한다는 것이다. 힙 자료구조가 현재 가장 가까운 노드를 저장해 놓는 역할(최소힙)을 하면서 시간을 선형에서 로그로 단축시킨다. 

 

* 사실 힙 자료구조는 우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 것이고, 우선순위 큐가 스택이나 큐와는 달리 우선순위가 가장 높은 데이터부터 꺼내는 역할을 하기에 이 상황에 사용하게 된 것이다.

* 리스트로 우선순위 큐를 구현할 경우 삽입 및 삭제 시간이 각각 $O(1)$, $O(N)$인 반면 힙(Heap)으로 구현했을 때에는 삽입과 삭제 시간이 모두 $O(logN)$이 된다. 

 

Dijkstra_advanced.py

# 개선된 다익스트라 알고리즘

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))   # 시작 노드
    distance[start] = 0
    while q:    # 큐가 비어있지 않다면 계속해서 수행
        dist, now = heapq.heappop(q)
        if distance[now] < dist:    # visited 테이블 역할
            continue    # 방문했었다면 아래 코드 수행 x
        for i in graph[now]:    # 현재 노드*와 인접한 노드들**에 대해서
            cost = dist + i[1]  # *을 거쳐가는 거리 계산
            if cost < distance[i[0]]:   # 출발점에서 *을 거쳐 **을 가는게 더 빠르다면
                distance[i[0]] = cost   # 갱신
                heapq.heappush(q, (cost, i[0]))

---

간단한 다익스트라랑 똑같다.

Heap에 (거리,노드) 정보가 들어오고 나가는 과정

간단한 다익스트라 알고리즘에서 사용된 방문처리 목적의 visited 테이블과 현 상황에서 최단거리가 가장 짧은 노드를 선택하는 역할의 get_smallest_node() 함수가 없는 대신 개선된 dijkstra() 함수에서 힙 자료구조를 사용하면서 이를 모두 처리한다. ☆

 

 

 

플로이드 워셜 알고리즘

다익스트라 알고리즘을 "한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우"에 사용할 수 있었다면, 

Floyd-Warshall 알고리즘은 "모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우"에 사용할 수 있는 알고리즘이다. 이건 소스코드도 간단하기 때문에 구현보다는 핵심 아이디어를 이해하는 것에 초점을 맞춰보자.

 

플로이드 워셜도 다익스트라 알고리즘과 마찬가지로 단계마다 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 다만 다른 점이라면 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다는 것이다.

 

한 50퍼만 이해된 것 같기에 이 알고리즘이 (모든~모든의 정보를 담기 위해) 2차원 테이블에 최단 거리 정보를 저장한다는 점과 그 테이블에 기록되어 있는 값을 점화식에 따라 갱신한다는 점, 그리고 그러한 방식이기에 다이나믹 프로그래밍 유형에 속한다는 점까지만 알아두고 점화식을 통해 단계별로 써보자.

$$D_{ab}=min(D_{ab}, D_{ak}+D_{kb})$$

"A에서 B로 가는 최소 비용" vs "A에서 K를 거쳐 B로 가는 비용" <- 이렇게 비교해서 더 작은 값으로 갱신한다는 내용을 담은 점화식이다.

이렇게 그래프가 있다.

두 간선 간의 연결관계를 담은 테이블을 작성한다.

n번째 노드를 거치는 모든 경우(6가지)에 대해 각각 값을 갱신한다.

 

이 경우 노드의 개수가 4개이므로 총 step 𝟜까지 알고리즘을 수행하게 된다. 모든 단계가 수행되었을 때, 최종적으로 이 테이블은 모든 노드에서 모든 노드로 가는 최단 거리 정보를 담고 있다. 노드의 개수가 N개 일 때 알고리즘상으로 N번의 단계를 수행하며, 단계마다 $O(N^2)$의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려하기 때문에 플로이드 워셜 알고리즘의 총 시간복잡도는 $O(N^3)$이다.

 

 

나동빈, ⌜이것이 취업을 위한 코딩 테스트다 with 파이썬⌟, 한빛미디어, 2020