최단 경로 알고리즘

최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다.

'한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우', '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우' 등의 다양한 사례가 존재한다.

1. Dijkstra(다익스트라)

1.1 개념

• 다익스트라는 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
• '음의 간선'이 없을 때 정상적으로 동작한다.
• 다익스트라는 기본적으로 그리디 알고리즘으로 분류된다. 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다.
• DP를 활용한 최단 경로 탐색 알고리즘이라고 할 수도 있다.
  • 여기서 DP가 적용되는 이유는, 굳이 한 번 최단 거리를 구한 곳은 다시 구할 필요가 없기 때문이다. 이를 활용해 정점에서 정점까지 간선을 따라 이동할 때 최단 거리를 효율적으로 구할 수 있다.

1.2. 과정

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

 

1.3. 시간 복잡도

• 우선순위 큐(heap 자료구조 기반)를 사용하면 시간 복잡도는 O(ElogV)이다.
  
  • 최대 E개의 간선 데이터를 힙에 넣었다가 다시 빼는 것으로 볼 수 있으므로 O(ElogE)라고 이해할 수 있다. 여기서 중복 간선을 포함하지 않는 경우 E는 항상 V^2보다 작다. 이 때 O(logV^2)은 O(logV)이고, 이는 O(logV)이다. 따라서 다익스트라 알고리즘의 전체 시간 복잡도는 간단히 O(ElogV)라고 할 수 있다.

자료구조	추출되는 데이터
스택(Stack)	가장 나중에 삽입된 데이터
큐(Queue)	가장 먼저 삽입된 데이터
우선순위 큐(Priority Queue)	가장 우선순위가 높은 데이터

• V는 노드의 개수이고 E는 간선의 개수를 의미한다.
• Pyhon에서는 heapq 라이브러리 사용, java에서는 PriorityQueue 사용

1.4. 코드(Python)

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

n,m = map(int, input().split())
graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)
start = int(input())

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

dijkstra(start)

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

2. Floyd-Warshall

Floyd-Warshall, 출처: 이것이 코딩테스트다

2.1. 개념

• 다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 최단 경로 알고리즘이다.
• 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다.
• 노드의 개수가 N개일 때 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려한다. 따라서 플로이드 워셜 알고리즘의 총시간 복잡도는 O(N^3)이다.
• 플로이드 워셜 알고리즘은 다익스트라 알고리즘과 다르게 2차원 리스트에 '최단 거리'정보를 저장한다는 특징이 있다.
• 플로이드 워셜 알고리즘은 다이나믹 프로그래밍이라는 특징이 있다. 
  • N번 만큼의 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신하기 때문
  • Dab = min(Dab, Dak + Dkb) => 점화식의 의미는 A에서 B로 가는 최소 비용과 A에서 K를 거쳐 B로 가는 비용을 비교하여 더 작은 값으로 갱신하겠다는 뜻이다.

2.2. 코드(Python)

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

 

---

참고

나동빈.『이것이 코딩테스트다 with 파이썬』.한빛미디어, 2020.

https://github.com/gyoogle/tech-interview-for-developer/blob/master/Algorithm/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC(Dijkstra).md 

GitHub - gyoogle/tech-interview-for-developer: 👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖

https://velog.io/@hyesoup/%EC%9D%B4%EA%B2%83%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8%EB%8B%A4-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

이것이 코딩테스트다 | 다익스트라 알고리즘