이것이 코테다 영상 강의 - 최단 경로 알고리즘

최단 경로 알고리즘 : 가장 짧은 경로를 찾는 문제

• 한 지점에서 다른 한 지점까지의 최단 경로 = 1:1
• 한 지점에서 다른 모든 지점까지의 최단 경로 = 1:N
• 모든 지점에서 다른 모든 지점까지의 최단 경로 = N:M

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

• 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산
• 음의 간선이 없을 때 정상적으로 동작
• 매 상황에서 가장 비용이 적은 노드를 선택(그리디)
• 최단 경로는 항상 DP가 기본으로 적용됌

다익스트라 최단 경로 동작 과정

• 출발 노드 설정
• 최단 거리 테이블 초기화(자기 자신은 '0', 나머지 노드 비용은 '$\infin$')
• 방문하지 않은 노드중에서 최단 거리가 가장 짧은 노드를 선택
• 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
• 3 & 4 반복
  • 거치는 노드마다 저장해서 갱신해준다. (DP)
  • 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것.

#다익스트라 알고리즘 간단한 구현 방법 
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 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
        for j in graph[now]:
            cost = distance[now] + j[1]
            if cost < distance[j[0]]:
                distance[j[0]] = cost

dijkstra(start)

for i in range(1, n + 1):
    if distance [i] == INF:
        print('INFINITY')
    else:
        print(distance[i])

다익스트라 성능 분석 : 총 $O(v)$번에 걸쳐 모든 노드 거리를 선형 탐색해야 된다.

• 즉, $O(v^2)$의 시간 복잡도다.
• 대부분의 (5,000개 이하 노드)문제는 이 알고리즘으로 해결 가능하다. (1초에 2,000만번 계산)

우선순위 큐(priorit queue) : 우선 순위가 가장 높은 데이터를 먼저 삭제하는 자료구조.

• 이를 위해 힙(heap) 자료구조 사용
  • 최소 힙(min heap)과 최대 힙(max heap)이 있다.
  • 다익스트라 뿐만 아니라 다양한 알고리즘에서 사용
  • 자체 트리가 있다.
• 리스트 방식으로 구현하면 삽입시간 $O(1)$에 삭제시간 $O(N)$이다.
• 힙 방식으로 구현하면 삽입시간 $O(\log N)$에 삭제시간 $O(\log N)$이다.

# min heap ex
import heapq

def heapsort(iterable):
    h = []
    result = []
    for value in iterable:
        heapq.heappush(h, value)
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

# max heap ex
import heapq
def heapsort(iterable):
    h = []
    result = []
    for value in iterable:
        heapq.heappush(h, -value)
    for i in range(len(h)):
        result.append(-heapq.heappop(h))
    return result

result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)

#improved dijkstra
import heapq
import sys
inut = 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]]:
            heapq.heappush(q, (cost, i[0]))

dijkstra(start)

for i in range(1, n + 1):
    if distance[i] == INF:
        print('INFINITY')
    else:
        print(distance[i])

우선순위를 포함한 다익스트라 성능 분석

• $O(E \log E)$ $E$ = 최대 간선 갯수; 중복 간선 포함을 안하면 $O(E \log V)$로 가능
• 10,000개 이상 노드도 처리 가능하다.

#warshall 
INF = int(1e9)

n = int(input())
m = int(input())
graph = [[INF] * (n + 1) for _ in range(n+1)]

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

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

플로이드 워셜 알고리즘

• 모든 노드에서 다른 모든 노드까지의 최단 경로 모두 계싼
• 2차원 테이블에 최단 거리 정보 저장 (DP에 속함)
• 3중 for문으로 2차원 테이블을 갱신하는 기법 $O(N^3)$ 입력 수가 (500개 정도)적을 시 적용 가능