[이.코.테] 최단 경로

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

• 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우
• 음의 간선이 없을 때
  • ex) GPS
• 그리디 알고리즘
  • 매번 '가장 비용이 적은 노드'를 선택하기 때문

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

방법1: 간단한 다익스트라

시간복잡도: $O(V^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 = [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] # 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]]: # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
                distance[j[0]] = cost
	
dijkstra(start)

방법2: 개선된 다익스트라

시간복잡도: $O(ElogV)$

1. 최대 E개의 간선 데이터를 힙에 넣었다가 다시 빼는 것이므로 $O(ElogE)$
2. 중복 간선을 포함하지 않는 경우, E는 항상 $V^2$보다 작음
3. $O(logV^2)$ → $O(2logV)$ → $O(logV)$
4. 따라서, $O(ElogV)$

힙 자료구조 사용 - 우선순위 큐 (Priority Queue, heapq)

• 첫 번째 원소를 기준으로 우선순위 설정
• 삽입 시간: $O(logN)$
• 삭제 시간: $O(logN)$
  

데이터가 N개일 때 - 리스트 vs 힙

• 리스트 삽입 & 삭제 시간: $O(N^2)$
• 힙 삽입 & 삭제 시간: $O(NlogN)$

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) 

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()) 
    graph[a].append((b,c))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start)) 
    distance[start] = 0
	
    while q:
        dist, now = heapq.heappop(q) 

        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]))

dijkstrat(start)

플로이드 워셜 알고리즘

• 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우
• 시간복잡도: $O(N^3)$
• DP 알고리즘
  • '점화식'에 맞게 2차원 리스트 갱신하기 때문
    • 점화식: $D_{ab} = min(D_{ab}, D_{ak}+D_{kb})$

INF = int(1e9)

n = int(input())
m = int(input())

graph = [[INF] * (n+1) for _ in range(n+1)] # 2차원 그래프

# 자기 자신으로 가는 비용 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 = 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])

💡 Tip

노드의 개수가 적다면 ⇒ 플로이드 워셜
노드 & 간선의 개수가 많으면 ⇒ 다익스트라