[이코테] chap9. 최단 경로

최단 경로

최단 경로(Shortest Path) : 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘.

• 최단 경로 문제는 보통 그래프를 이용해 표현한다.
  각 지점(국가, 학교) -> '노드', 지점간 연결된 도로 ->'간선'으로 표현된다.
• 코테에선 최단 경로를 출력하는 문제 보단, '최단 거리'를 요구하는 문제가 많이 출제된다.
  학부 수준의
  • 다익스트라(Dijkstra) 최단 경로 알고리즘
  • 플로이드 워셜(Floyd-Warshall) 알고리즘
  • 벨만포드 알고리즘
• 최단 거리 알고리즘엔 3가지가 있지만, 그 중에서도 코테에 자주 등장하는 것은 2가지이므로 이것만 우선적으로 설명한다.
• 최단 경로 알고리즘의 대표적 유형 3가지
  1. 한 지점에서 다른 특정 지점까지의 최단 경로 (다익스트라)
  2. 한 지점에서 모든 지점까지의 최단 경로
  3. 모든 지점에서 모든 지점까지의 최단 경로 (플로이드 워셜)

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

특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.

• 음의 간선이 없을 때 정상적으로 작동한다.
• 각 노드에 대해 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하며, 리스트를 계속 갱신한다는 특징을 갖는다.
  (* 1차원 리스트 : 최단 거리 테이블, 노드 개수의 크기만큼 선언한 1차원 리스트)
• 최단 거리 테이블의 초기화는 '무한(10억 = int(10e9))'
• 우선순위 큐를 이용하여 작성할 수 있다.(heapq) [개선된 다익스트라 알고리즘]
• 구현 방법은 2가지
  1. 구현하기 쉽지만 느리게 동작 -> 간단한 다익스트라 알고리즘
  2. 구현하기 어렵지만 빠르게 동작 -> 개선된 다익스트라 알고리즘

알고리즘 원리

1. 출발 노드를 설정
2. 최단 거리 테이블을 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여, 최단 거리 테이블을 갱신한다.
5. 위과정에서 3, 4번을 반복한다.

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

• 시간 복잡도 $O(V^2)$ (V: 노드의 개수)
  : O(V)번에 걸쳐 최단 거리가 가장 짧은 노드를 매번 선형 탐색하고, 현재 노드와 연결된 노드를 일일이 확인 하므로.
  -> 코테에선 전체 노드 개수가 5000개 이하면 문제를 풀 수 있지만, 10,000개가 넘어가면 해결하기 어렵다.
• 1초에 2천만번 처리되면 합리적

import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
# 각 노드 배열 생성
graph = [[] for i in range(n + 1)]
# 방문한 적이 있는지 체크하는 목적의 리스트를 만들기
visited = [False] * (n + 1)
# 최단 거리 테이블을 모두 무한으로 초기화 - distance
distance = [INF] * (n + 1)

# 모든 간선 정보를 입력받기
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
    visited[start] = True 
    for j in graph[start]: # 시작 노드와 연결된 것의 거리 갱신
        distance[j[0]] = j[1]
    # 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
    for i in range(n - 1):
        # 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
        now = get_smallest_node()
        visited[now] = True
        # 현재 노드와 연결된 다른 노드를 확인
        for j in graph[now]:
            cost = distance[now] + j[1]
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[j[0]]: # 기존 table 값 보다 작은 경우 갱신
                distance[j[0]] = cost

# 다익스트라 알고리즘을 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

개선된 다익스트라 알고리즘(우선순위 큐)

• 시간 복잡도 : $O(ElogV)$ E - 간선의 개수, V - 노드의 개수
• 간단한 다익스트라와의 차이점
  • 간단한 다익스트라 알고리즘은 '최단 거리가 가장 짧은 노드'를 찾기 위해
    매번 최단 거리 테이블을 선형 탐색한다. -> O(v), get_smallest_node()
    이 부분을 heapq인 우선순위 큐를 이용하여 logN의 시간이 걸리도록 줄여준다.
    시간 복잡도 설명 (내가 보려고 써둠)
  • while문이 반복되는 조건인 q는 E의 정보들을 넣는 것이다. 그러므로 전체 다익스트라 알고리즘은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사하다.
  • 따라서 앞에서 말했듯이 힙에 E개의 데이터를 모두 넣고, 이후에 모두 빼는 과정은 O(ElogE)이다.(힙의 삽입 삭제의 시간 복잡도 logN)
    이때 중복 간선을 포함하지 않는 경우, E는 항상 V^2보다 작다. (V <= E < V^2)
    선택된 노드의 인접한 노드를 확인하는 것이므로, O(logE) -> O(logV^2) -> O(2logV) -> O(logV)
    => 따라서 E들의 인접한 노드를 확인하는 것이므로, O(ElogV)가 된다.
    앞에 E는 왜 안바꿔주냐면, cost < distance[i] 부분에서 작으면 아예 검사 안하니까 E보다 작게 push 될 수 밖에 없어서 구럼!!

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(n + 1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

# 모든 간선 정보를 입력받기
for _ in range(m):
    a, b, c = map(int, input().split())
    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    graph[a].append((b, c))

def dijkstra(start):
    q = []
    # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q: # 큐가 비어있지 않다면
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(q)
        # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
          # 다른 노드에 연결되어 있던 now, cost(dist + i[1])가 큐에 들어와있지만, 이미 처리되어 distance[now]가 있는 경우
        if distance[now] < dist:
            continue
        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for i in graph[now]:
            cost = dist + i[1]
            # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

# 다익스트라 알고리즘을 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(distance[i])

플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 것

• DP를 이용하여 '단계마다 거쳐가는 노드'를 기준으로, 최단 거리 테이블을 갱신하는 방식으로 동작한다.
  다음의 점화식만 기억하면 큰 어려움 없이 구현 가능하다.

$$Dab = min(Dab, Dak + Dkb)$$

• 다음과 같이 3중 반복문을 이용해 구현할 수 있다.

for k in range(1, n + 1): 
	for a in range(1, n + 1): 
    	for b in range(1, n + 1): 
        	adj[a][b] = min(adj[a][b], adj[a][k] + adj[k][b])

• 시간 복잡도: $O(V^3)$

코드 구현

INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정

# 노드의 개수 및 간선의 개수를 입력받기
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

# 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for _ in range(m):
    # A에서 B로 가는 비용은 C라고 설정
    a, b, c = map(int, input().split())
    graph[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):
        # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
        if graph[a][b] == 1e9:
            print("INFINITY", end=" ")
        # 도달할 수 있는 경우 거리를 출력
        else:
            print(graph[a][b], end=" ")
    print()