최단 경로

최단 경로

말 그대로 가장 짧은 경로를 찾는 알고리즘
학교 알고리즘 수업시간에 다익스트라 알고리즘과 플로이드 워셜 알고리즘 이 두 가지를 배웠었는데, 이코테에서도 이 두 가지를 설명하고있다.

1. 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우 - 다익스트라 알고리즘
2. 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야하는 경우 - 플로이드 워셜 알고리즘

다익스트라 알고리즘

다익스트라 알고리즘은 음의 간선이 없을 경우 정상적으로 동작한다. 음의 간선이란 0보다 작은 값을 가지는 간선을 의미한다.

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

3번에서 방문되지 않은 노드 중에서 가장 짧은 노드를 선택하여 4번을 수행하므로, 다익스트라 알고리즘은 그리디 알고리즘으로 볼 수 있다. 다익스트라 알고리즘은 간단한 방법과 우선순위 큐를 이용하여 개선된 방법으로 설계할 수 있다.

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

# n은 노드의 개수, m은 간선의 개수
n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n+1)]
visited = [False]*(n+1)
distance = [float('inf')]*(n+1)

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

# 방문하지 않은 노드 중, 가장 짧은 노드의 인덱스 반환
def smallest_node():
    mini = float('inf')
    idx = 0
    for i in range(1,n+1):
        if visited[i] == False and mini > distance[i]:
            mini = distance[i]
            idx = i
    return idx

def dijkstra(start):
    distance[start] = 0
    visited[start] = True
    # 시작 노드에 연결된 점들까지 거리 입력
    for j in graph[start]:
        distance[j[0]] = j[1]
    # 시작 노드를 제외했으니 n-1
    for _ in range(n-1):
        min_idx = smallest_node()
        visited[min_idx] = True
        for j in graph[min_idx]:
            # min_idx의 노드를 거쳐서 가는 거리가 더 짧으면 갱신 
            if distance[j[0]] > distance[min_idx]+j[1]:
                distance[j[0]] = distance[min_idx]+j[1]

dijkstra(start)

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

이 알고리즘의 시간복잡도는 O((노드의 개수)^2)이다. 최단 거리가 가장 짧은 노드를 매번 탐색하고, 그 노드와 연결된 노드들을 확인해야하기 때문이다.
코딩 테스트에서 전체 노드의 개수가 5000개 이하라면 이 알고리즘으로 풀 수 있지만, 10000개가 넘어가면 이 코드를 사용하면 안된다.

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

import heapq

# n은 노드의 개수, m은 간선의 개수
n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n+1)]
distance = [float('inf')]*(n+1)

# 간선 정보 입력받기
for _ in range(m):
    # a번 노드에서 b번 노드로 가는 비용이 c
    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, min_idx = heapq.heappop(q)
        if distance[min_idx] < dist:
          continue
        for i in graph[min_idx]:
            if distance[i[0]] > dist+i[1]:
                distance[i[0]] = dist+i[1]
                heapq.heappush(q, (distance[i[0]],i[0]))

dijkstra(start)

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

구조가 bfs 알고리즘과 약간 비슷하다.

개선된 다익스트라 알고리즘은 가장 가까운 노드를 저장하기 위한 목적으로 우선순위 큐를 이용한다. 따라서 최단 거리가 가장 짧은 노드를 선택하는 함수인 smallest_node함수가 필요없다.

여기서 힙 자료구조를 이용하면 단일 데이터의 삽입과 삭제 연산을 O(log(N))에 수행하기 때문에, (노드의 수를 V라고 하고, 간선의 수를 E라고 하면) 간선의 수만큼 반복하면 O(E*log(E))이 걸린다.

추가적으로, 중복 간선을 포함하지 않는 경우, E는 항상 V^2보다 작다. (왜냐하면, E <= V(V-1)) 따라서 O(E2log(V))로 표현할 수 있고, 정리하면 O(Elog(V))로 나타낼 수 있다.

플로이드 워셜 알고리즘

D(ab) = min(D(ab), D(ak)+D(kb))

위의 점화식을 모든 a(출발점),b(도착점),k(경유하는 점)에 대하여 적용하여 다이나믹 프로그래밍을 활용하는 알고리즘이다.
따라서 모든 지점에서 다른 모든 지점까지의 최단거리를 계산한다.

n, m = map(int, input().split())
dp = [float('inf')*(n+1) for _ in range(n+1)]

for i in range(1,n+1):
    dp[i][i] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    dp[a][b] = c

for k in range(1,n+1):
    for i in range(1,n+1):
        for k in range(1,n+1):
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])

for i in range(1,n+1):
    for j in range(1,n+1):
        if dp[i][j] == float('inf'):
            print('inf')
        else:
            print(dp[i][j])

모든 출발점, 도착점, 경유하는 점을 조사하여 연산하므로, 시간복잡도는 O(N^3)이다.