최단경로 Shortest Path

" 가장 짧은 경로를 찾는 알고리즘이다 " 

- "길 찾기" 문제라고도 불린다.

- 그래프를 이용해 표현(= 각 지점은 그래프에서 " 노드 ", 지점간 연결된 도로는 그래프에서 "간선")

- 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제

 

<CASE>

1. 한 지점에서 다른 특정 지점까지 최단 경로를 구해야 하는 경우 - 다익스트라

2. 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 - 플로이드 워셜

<플로이드 워셜>

https://cord-ai.tistory.com/167

플로이드 워셜 Floyd-Warshall 알고리즘

 

<최단 알고리즘 종류>
다익스트라 최단 경로, 플로이드 워셜, 벨만 포드 알고리즘

Greedy그리디, 다이나믹 프로그래밍 => 최단 경로 알고리즘에 그대로 적용됨
최단 경로 알고리즘은 그리디 및 다이나믹 프로그래밍 알고리즘의 한 유형으로 볼 수 있다.
그리디 - 다익스트라
플로이드 워셜 - 다이나믹

 

다익스트라(데이크스트라) 알고리즘 Dijkstra

- 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를

구해주는 알고리즘

- 시간 복잡도 O(V²), V= 노드의 개수

- " 음의 간선 "이 없을 때 정상적으로 동작한다.

"음의 간선"이란???
0보다 작은 값을 가지는 간선을 의미하는데, 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로
다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다.

- 기본적으로 그리디 알고리즘으로 분류됨

=> 매번 "가장 비용이 적은 노드"를 선택해서 임의의 과정을 반복하므로

- 그래프 문제로 유명한 최소 신장 트리 문제를 풀 때에도 일부 알고리즘(Prim 알고리즘)의 구현이

다익스트라 알고리즘의 구현과 흡사하다는 특징이 있다.

<그래프 문제, Prim 알고리즘>

 

1. 출발 노드(=도시)를 설정한다.
2. 최단 거리 테이블을 초기화한다.(= 1차원 리스트)
3. 방문하지 않은 노드(=도시) 중에서 최단 거리가 가장 짧은 노드를 선택한다.
(= 1차원 리스트의 모든 원소 확인, 순차 탐색)
(= 만약 최단 거리가 같은 값인 노드가 있다면 일반적으로 번호가 작은 노드를 선택한다.)
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5. 3, 4번 과정을 반복

- "각 노드에 대한 현재까지의 최단 거리 정보"를 항상 1차원 리스트에 저장하며 리시트를 계속 갱신한다
- 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인한다.
- 이후 현재 처리하고 있는 노드와 인전합 노드로 도달하는 더 짧은 경로를 찾으면 " 더 짧은 경로"라고 판단하는 것

3번 과정을 확인해 그 노드에 대하여 4번 과정을 수행한다는 점에서 " 그리디 알고리즘 "으로 볼 수 있다.

https://www.youtube.com/watch?v=HFapeLxvdNg 

<구현 방법>

1. 구현하기 쉽지만 느리게 동작하는 코드

2. 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드

(= * 2번 방법을 정확히 이해하고 구현할 수 있을 때까지 연습해야한다 *)

 

<하나씩 해볼 것>

1. 1번 노드와 연결된 노드 2, 3, 4

2. 2 = (0 + 2), 3 = (0+5), 4 = (0+1) 갱신

3. 갱신 후 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택(= 4)

4. 3번 반복

= 갱신할 값이 기존 값보다 크면 갱신하지 않는다. (최솟값으로 갱신)

 

 

 

 

<1번 노드로부터 출발했을 때 각 노드까지 가기 위한 최단 경로>

노드 번호	1	2	3	4	5	6
거리	0	2	3	3	2	4

" 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택 " 하는 과정을 반복하는데, 이렇게 선택된 노드는 "최단 거리"가 완전히 선택된 노드이므로, 더 이상 알고리즘을 반복해도 최단 거리가 줄어들지 않는다.

2번째 4번 노드가 선택되어서 4번 노드를 거쳐서 이동할 수 있는 경로를 확인하는데,
이후 다음 노드가 진행되어도 4번 노드에 대한 최단 거리는 더 이상 감소하지 않는다.

다익스트라는 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것

그렇기 때문에, 마지막 노드에 대해서는 해당 노드를 거쳐 다른 노드로 가는 경우를 확인할 필요가 없다.

= 위의 예시에서 마지막 노드를 수행할 때 이미 5개 노드에 대한 최단 거리가 확정된 상태이므로 더 이상 테이블이 갱신될 수 없기 때문임

 

<방법 1>

시간복잡도 O(V²)

- 총 O(V)번 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 하고, 현재 노드와 연결된 노드를 매번 일일이 확인하기 때문

- 전체 노드의 개수가 5,000 이하라면 해당 코드로 문제를 풀 수 있지만 10,000개가 넘어가면 문제를 해결하기 어렵다. => 방법 2

# 방법 1 다익스트라
## 노드에 대한 정보를 담는 리스트 생성
## 방문 여부
## 최단 거리 테이블 모두 무한으로 초기화
## 순차 탐색 = 값 갱신
'''
(노드개수, 간선의 개수)
(시작노드)
(간선 정보 a, b, c)
6 11 
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2

0
2
3
1
2
4
'''
import sys

# 입력되는 데이터의 수가 많다는 가정하에 해당 방법 적용
input = sys.stdin.readline

# 대부분 문제에서는 그래프의 간선 길이 정보를 줄 때 1억 미만값으로 준다.
INF = int(1e9) # 무한을 의미하는 값으로 10억 설정

n,m = map(int, input().split())

# 시작 노드 
start = int(input())

# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
graph = [[] for i in range(n+1)]

# 방문 여부
visited = [False] * (n+1)

# 최단 거리 테이블 모두 무한으로 초기화
d = [INF] * (n+1)

# 모든 간선 정보 입력
for _ in range(m):
    a, b, c = map(int, input().split())

    # a번 노드에서 b번 노드로 가는 비용이 c라는 의미
    graph[a].append((b,c))

print(graph)
# [[], [(2, 2), (3, 5), (4, 1)], [(3, 3), (4, 2)], [(2, 3), (6, 5)], [(3, 3), (5, 1)], [(3, 1), (6, 2)], []]

# 방문하지 않은 노드이면서 시작 노드와 최단 거리인 노드 반환
def get_smallest_node():
    min_value = INF
    index = 0 # 가장 최단 거리가 짧은 노드(= index)

    for i in range(1, n+1):
        # 테이블 value 갱신 및 방문하지 않았다면
        if d[i] < min_value and not visited[i]:
            # 갱신
            min_value = d[i]
            index = i

    return index

def dijkstra(start):
    # 시작 노드 초기화
    d[start] = 0
    visited[start] = True

    # 해당 노드 값
    for i in graph[start]:
        # i[0] == node
        # i[1] == 해당 노드와의 거리 값
        d[i[0]] =i[1]

    # 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
    for j in range(n-1):

        # 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
        now = get_smallest_node()
        visited[now] = True

        #현재 노드와 연결된 다른 노드를 확인
        for v in graph[now]:
            cost = d[now] + v[1]

            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < d[v[0]]:

                # 테이블 갱신
                d[v[0]] = cost

dijkstra(start)
print(d)
# [1000000000, 0, 2, 3, 1, 2, 4]

for i in range(1, n+1):

    # 도달할 수 없는 경우
    if d[i] == INF:
        print("무한")

    # 시작노드에서 부터 도달할 수 있는 경우의 거리를 모두 출력
    else:
        print(d[i])

 

<방법 2>

시간복잡도 O(ElogV), E = 간선의 개수, 인접 리스트 방식

why???

한 번 처리된 노드는 더 이상 처리되지 않는다. 다시 말해 큐에서 노드를 하나씩 꺼내 검사하는 반복문(while)은
노드의 개수 V 이상의 횟수로 반복되지 않는다. 또한, V번 반복될 때마다 각각 자신과 연결된 간선들을 모두 확인한다.
따라서, "현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인"하는 총횟수는 총 최대 간선의 개수(E)만큼 연산이 수행될 수 있다.
따라서, 전체 다익스트라 최단 경로 알고리즘은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사하다고 볼 수 있다. 앞에서 말했듯이 힙에 N개의 데이터를 모두 넣고, 이후에 모두 빼는 과정은 O(NlogN)이다.
= <힙 자료구조 참조>
간단하게 생각하면 다익스트라 알고리즘의 시간 복잡도는 최대 E개의 간선 데이터를 힙에 넣었다가 다시 빼는 것으로 볼 수 있으므로 O(ElogE)임을 이해할 수 있다.
이때 중복 간선을 포함하지 않는 경우, E는 항상 V²보다 작다. 왜냐하면, 모든 노드끼리 서로 다 연결되어 있다고 했을 때 간선의 개수를 약 V²으로 볼 수 있고 E는 항상 V²이하이기 때문이다. 
다시 말해 logE는 logV²보다 작다. 이때 O(logV²)은 O(2logV)이고, 이는 O(logV)이다.
따라서, 다익스트라 알고리즘의 전체 시간 복잡도를 간단히 O(ElogV)라고 볼 수 있다.

 

- 개선된 다익스트라 알고리즘에서는 힙(Heap) 자료구조를 사용한다.

- 힙 자료구조를 이용하게 되면 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있다.

<힙 자료구조>

https://cord-ai.tistory.com/166

힙 Heap 자료구조

- 우선순위 큐를 이용해서 시작 노드로부터 "거리"가 짧은 노드 순서대로 큐에서 나올 수 있도록 다익스트라 알고리즘 작성

- Python에서는 튜플 (거리, 노드)의 형태로 우선순위 큐에 넣는다.

- 라이브러리 heapq는 원소로 튜플을 입력받으면 튜플의 첫 번째 기준으로 우선수위 큐를 구성한다.

- 따라서 거리순으로 졍렬된다.

(= 우선순위 큐는 튜플의 첫 번째 원소(거리)가 작은 순서대로 왼쪽부터 기록된다.)

# 방법 2
## 기본 원리는 동일
## 1차원 리스트(최단 거리 테이블)는 그대로 이용
## 현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 이용

## get_smallest_node()를 작성할 필요가 없음 + 방문 여부 X
# = 최단 거리가 가장 짧은 노드를 선택하는 과정을 다익스트라 최단 경로 함수 안에서
# 우선순위 큐를 이용하는 방식으로 대체할 수 있기 때문

import sys
import heapq

# 입력되는 데이터의 수가 많다는 가정하에 해당 방법 적용
input = sys.stdin.readline

# 대부분 문제에서는 그래프의 간선 길이 정보를 줄 때 1억 미만값으로 준다.
INF = int(1e9) # 무한을 의미하는 값으로 10억 설정

n,m = map(int, input().split())

# 시작 노드 
start = int(input())

# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
graph = [[] for i in range(n+1)]

# 최단 거리 테이블 모두 무한으로 초기화
d = [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))
    d[start] = 0

    while q: # q가 비어있지 않다면

        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist, now = heapq.heappop(q)
        
        # 현재 꺼낸 원소의 거리 값(dist)이 테이블에 기록된 값(d[now]) 보다 크다면
        # 현재 노드가 이미 처리된 적이 있는 것으로 간주할 수 있다.
        if d[now] < dist:
            continue

        # 현재 노드와 연결된 다른 인접한 노드들을 확인
        for i in graph[now]:
            # i[1] i 노드에서의 거리 값
            cost = dist + i[1]

            # 현재 노드를 거쳐서, 다른 노드(인접 노드)로 이동하는 거리가 더 짧은 경우
            if cost < d[i[0]]:
                # 테이블 갱신
                d[i[0]] = cost

                # 값이 갱신될 때마다 기록될 수 있게
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)
print(d)
for i in range(1, n+1):

    # 도달할 수 없는 경우
    if d[i] == INF:
        print("무한")

    # 시작노드에서 부터 도달할 수 있는 경우의 거리를 모두 출력
    else:
        print(d[i])