[알고리즘] 이코테(6) - 최단 경로 알고리즘 (다익스트라, 플로이드워셜)

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬, 나동빈, 2021

강의: https://youtu.be/acqm9mM1P6o?si=paoazc7Qx2lqr39R

---

최단 경로 알고리즘

가장 짧은 경로를 찾는 알고리즘.

 

다양한 문제 상황이 있다.

1. 한 지점에서 다른 한 지점까지의 최단 경로
2. 한 지점에서 다른 모든 지점까지의 최단 경로
3. 모든 지점에서 다른 모든 지점까지의 최단 경로

각 지점은 그래프에서 노드로 표현한다.

지점 간 연결 도로는 그래프에서 간선으로 표현한다.

 

다익스트라 Dijkstra

출처: GeeksforGeeks

요약

특정 노드에서 다른 모든 노드로 가는 최단 경로를 계산.

음의 간선이 없는, 현실 세계의 도로에서 정상적으로 동작.

 

그리디 알고리즘으로 분류.

매 상황에서 가장 비용이 적은 노드를 선택하여 과정을 반복하기 때문.

 

동작 과정

1. 출발 노드를 설정
2. 최단 거리 테이블을 최댓값(예컨대 INF)으로 초기화 (각 노드에 대한 현재까지의 최단 거리 정보를 갖고 있음)
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
4. 3번에서 선택한 노드를 거쳐, 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
5. 모든 노드를 방문할 때까지 3번과 4번을 반복

구현1. 기본적인 다익스트라

INF = int(1e9) # 무한의 거리를 나타내기 위해 10억을 설정

n, m = map(int, input().split())
start = int(input()) # 시작 노드
graph = [[] for _ in range(n+1)] # 연결 정보 담는 리스트
visited = [False] * (n+1) # 방문 체크 리스트
distance = [INF] * (n+1) # 시작 노드부터 특정 노드까지의 최단 거리 테이블. INF로 초기화.

for _ in range(m): # 모든 간선 정보 입력
    a, b, c = map(int, input().split()) # a번 노드 -> b번 노드 (비용 c)
    graph[a].append((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 # 시작 노드부터 시작 노드까지의 최단 거리는 0으로 갱신
    visited[start] = True # 방문 처리
    
    for adjacent_node_of_start in graph[start]: # 시작 노드와 인접한 노드의 최단 거리 갱신
        distance[adjacent_node_of_start[0]] = adjacent_node_of_start[1]
        
    for i in range(n-1): # n-1인 이유. 시작 노드X. 마지막 노드X
        now = get_smallest_node() # 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드
        visited[now] = True # 방문 처리
        
        for adjacent_node in graph[now]: # 선택한 노드와 인접한 노드 확인
            cost = distance[now] + adjacent_node[1] # 시작~선택 + 선택~인접
            if cost < distance[adjacent_node[0]]: # cost가 시작~인접보다 작을 경우 갱신
                distance[adjacent_node[0]] = cost
                
dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print("도달할 수 없는 신기루")
    else:
        print(distance[i])

 

1번 방법의 특징

O(V)번에 걸쳐서 get_smallest_node()를 호출하여, 매번 선형 탐색을 해야 한다.

따라서 전체 시간 복잡도는 O(V^2)이다.

 

python은 대략 1초에 20,000,000 연산이 가능하므로 노드 개수가 5,000 개면 간당간당하다.

우선순위 큐를 이용하여 개선이 필요하다.

 

잠시 자료 구조의 바다에 빠져보자.

풍덩 ~

---

우선순위 큐 Priority Queue

우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료 구조.

 

python은 표준 라이브러리 형태로 지원한다.

나의 이데아 swift는 지원하지 않는다. 함부로 다가갈 수 없는 매력이 있다.

우선순위 큐 구현 방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙	O(logN)	O(logN)

 

힙 Heap

우선순위 큐를 구현하기 위해 필요한 자료 구조이다.

최소 힙(Min Heap)과 최대 힙(Max Heap)이 있다.

 

완전 이진 트리(complete binary tree)의 일종.

힙은 느슨한 정렬 상태를 유지한다.

부모 노드의 key(노드가 저장하는 값)가 자식 노드의 key보다 항상 작은-최소 힙(큰-최대 힙) 상태의 이진 트리.

 

이진 트리 binary tree

이진 트리의 종류 (출처: tutorialcup)

출처: velog.io/@dlgosla

 

모든 노드가 둘 이하(0, 1, 2)의 자식을 가진 트리이다.

위 그림과 같이 다양한 종류가 있다.

---

 

많은 자료 구조를 만나고 왔다.

 

이진 트리 -> 완전 이진 트리 -> 힙 -> 우선 순위 큐 -> 개선된 다익스트라 알고리즘.

이렇듯 여러 단계를 거쳐 다익스트라를 개선시킬 수 있다.

 

핵심은 단계마다 방문하지 않은 노드 중에서, 시작 노드로부터 최단 거리가 가장 짧은 노드를 선택하기 위해 힙을 사용하는 것이다.

 

구현2. 개선된 다익스트라

import heapq

INF = int(1e9)

n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n+1)]
distance = [INF] * (n+1)
# 방문 처리 배열을 만들지 않는다. 단계마다 순차 탐색하는 것이 아니라 우선순위 큐에서 pop()하므로.

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start)) # 시작 노드 -> 시작 노드의 최단 거리는 0으로 갱신. 큐에 삽입.
    distance[start] = 0
    
    while q: # 큐가 텅텅 빌 때까지 반복
        dist, now = heapq.heappop() # 최단 거리(dist)를 기준으로 우선순위 큐에서 bubble pop

        if distance[now] < dist: # distance[now] == 현재까지 확정된 최소 거리, dist == 현재 탐색에서 최소 거리
            continue # 확정된 최소 거리가 더 짧으면, 이미 방문한 셈 치고 continue
        
        for adjacent_node in graph[now]:
            cost = dist + adjacent_node[1] # 현재 탐색에서, 탐색 중인 노드의 최소 거리 + 인접 노드의 최소 거리
            if cost < distance[adjacent_node[0]]: # cost가 인접 노드의 확정된 최소 거리보다 짧다면 갱신
                distance[adjacent_node[0]] = cost
                heapq.heappush(q, (cost, adjacent_node[0]])

dijkstra(start)

for i in ragne(1, n+1):
    if distance[i] == INF:
        print("영영 닿을 수 없음")
    else:
        print(distance[i])

 

개선된 방법의 특징

시간 복잡도는 O(ElogV)이다.

E는 Edge(간선), V는 Vertex(정점, 노드).

 

모든 노드를 검사하는 while문은 간선의 개수 E에 따라 실행 횟수가 결정된다.

왜 why? 간선의 개수만큼 큐에 넣으니까.

 

전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산(O(logN))과 유사하다.

E개의 원소에 대하여 O(logE)의 연산을 수행한다.

즉, 시간 복잡도는 O(ElogE)이다.

 

동시에 이것은 O(ElogV)와 같다.

왜 why? 실제 그래프에서 모든 노드가 서로 연결되어 있다면, 최대 간선 수는 V*(V-1)/2이다.

따라서 다음의 식이 성립한다.

O(ElogE) -> O(ElogV^2) -> O(2ElogV) -> O(ElogV)

 

 

플로이드-워셜 Floyd-Warshall

플로이드 워셜. 단순 연결 관계로 초기화한 상태. (출처: 유튜브 캡처)

요약

모든 노드에서 다른 모든 노드로 가는 최단 경로를 모두 계산.

 

다익스트라와 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행.

단, 단계마다 방문하지 않는 노드 중 최단 거리 노드를 찾는 과정은 필요X (다익스트라에서 get_smallest_noe()로 수행했던 그것)

 

2차원 테이블에 최단 거리 정보를 저장.

다이나믹 프로그래밍 유형에 속함.

 

동작 과정

1. 2차원 최단 거리 테이블을 최댓값(예컨대 INF)으로 초기화
2. 각 단계마다 특정한 노드 k를 거쳐가는 경우를 확인
   1.  a -> b 최단 거리보다, a -> k  + k -> b가 더 짧은지 검사
   2. 점화식(D는 거리): Dab = min(Dab, Dak + Dkb)
3. 모든 노드를 방문할 때까지 2번을 반복

구현: 플로이드 워셜

INF = int(1e9)

n, m = map(int, input().split()) # n은 노드의 개수, m은 간선의 개수
graph = [[INF] * (n + 1) for _ in range(n + 1)] # 최단 거리 정보를 저장할 2차원 리스트 INF로 초기화

for a in range(1, n+1): # 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0
            
for _ in range(m): # 각 간선에 대한 정보를 입력 받아, 최단 거리 테이블 갱신
    a, b, c = map(int, input().split())
    graph[a][b] = c # a에서 b로 가는 비용을 c라고 설정
    
for k in range(1, n+1): # 점화식에 따라 플-워 수행
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

for a in range(1, n+1):
    for b in range(1, n+1):
        if graph[a][b] == INF:
            print("INFINITY", end = " ")
        else:
            print(graph[a][b], end = " ")
    print()

 

플로이드 워셜의 특징

노드의 개수가 N개일 때 알고리즘을 N번 수행한다.

각 단계마다 O(N^2)의 연산을 통해, 현재 선택된 노드를 거쳐 가는 모든 경로를 고려한다.

 

따라서 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N^3)이다.