[최단 경로] 알고리즘 개념

가장 빠르게 도달하는 방법

최단 경로 알고리즘 = 가장 짧은 경로 찾기 = 길 찾기

• ex)
  한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우
  모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 등
• 대표적인 예시 : 다익스트라 최단 경로, 플로이드 워셜 알고리즘

보통 그래프를 이용하여 표현 : 지점 = 노드 & 도로 = 간선

 

 

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

특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘

 

특징

• '음의 간선'이 없을 때 정상적으로 동작
• GPS 소프트웨어의 기본 알고리즘으로 채택
• 그리디 알고리즘으로 분류 : '가장 비용이 적은 노드' 선택
• '각 노드에 대한 현재까지의 최단 거리' 정보를 1차원 리스트에 저장 & 갱신

 

알고리즘의 원리

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

 

구현 방법

1. 구현하기 쉽지만 느리게 동작하는 코드
2. 구현하기에 조금 더 까다롭지만 빠르게 동작하는 코드 → 가능할 때까지 연습!

 

알고리즘 동작 원리

• 1번 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 문제
• 초기 상태에서는 다른 모든 노드로 가는 최단 거리를 '무한'으로 초기화
  * 파이썬에서는 '무한'을 int(1e9)로 주로 초기화

 

0. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택

 

* 현재 노드 하늘색, 방문했던 노드 회색

 

1. 1번 노드를 거쳐 다른 노드로 가는 비용 계산
    각각 더 짧은 경로를 찾으면, 새로운 값으로 갱신

 

2. 계속해서 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 → 현재 4번 노드
    4번 노드를 거쳐 갈 수 있는 노드 확인 & 갱신 : 3번 노드 (5 → 4), 5번 노드 (무한 → 2)

 

3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 → 현재 2번 노드
    2번 노드를 거쳐 갈 수 있는 노드 확인 & 갱신할 수 있는 방법 없으므로 그대로
    * 2, 5번 노드 모두 최단 거리일 땐, 일반적으로 번호 작은 노드 선택

   

 

4. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 → 현재 5번 노드

    2번 노드를 거쳐 갈 수 있는 노드 확인 & 갱신 : 3번 노드 (4 → 3), 6번 노드 (무한 → 4)

 

5. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 → 현재 3번 노드
    3번 노드를 거쳐 갈 수 있는 노드 확인 & 갱신할 수 있는 방법 없으므로 그대로

 

 

6. 최종 최단 거리 테이블

 

결과 해석

• 최단 거리 테이블을 해석하면, 각 노드에 대한 최단 경로가 각각 2, 3, 1, 2,라는 의미
• 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것

 

방법 1. 간단한 다익스트라 알고리즘

• 시간 복잡도 : O(V^2)    # V는 노드의 개수
• 처음에 각 노드에 대한 최단 거리를 담는 1차원 리스트 선언
• 단계마다 '방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택'
  → 매 단계마다 1차원 리스트 모든 원소 확인(순차 탐색)
• input()을 더 빠르게 동작하는 sys.std.readline()으로 치환하여 사용
• 모든 리스트는 (노드의 개수 + 1)의 크기로 할당하여, 노드 번호로 바로 리스트 접근

# 간단한 다익스트라 알고리즘 소스코드
import sys
input = sys.stdin.readline
INF = int(1e9)    # 무한을 의미하는 값으로 10억을 설정

# 변수 : 노드의 개수 N, 간선의 개수 M, 시작 노드 start, 노드 연결 정보 graph, 방문 리스트 visited, 최단 거리 테이블 distance
# 노드의 개수, 간선의 개수를 입력받기
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]
    # 시작 노드를 제외한 전체 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[now] + j[1]
                distance[j[0]] = cost

# 다익스트라 알고리즘 수행
dijkstra(start)

# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우, 거리를 출력
    else:
        print(distance[i])

 

해석

변수

: 노드의 개수 N, 간선의 개수 M, 시작 노드 start, 노드 연결 정보 graph, 방문 리스트 visited, 최단 거리 테이블 distance

 

1. 변수 입력받기

ㄴ 노드 개수N , 간선의 개수 M : map(int, input().split())

ㄴ 시작 노드 start

ㄴ 노드 연결 정보 graph : [ ] 빈 리스트로 초기화

ㄴ 방문 리스트 visited : [False] 방문 안함으로 초기화

ㄴ 최단 거리 테이블 distance : [INF] 무한으로 초기화

2. 노드 연결 정보 입력받기 : graph[a].append((b, c))

ㄴ graph[a] = (b, c)    # a → b 노드로 이동, c 비용

------------------------ 최단 거리 노드 반환 함수 ------------------------

ㄴ 최단 거리 & 방문하지 않은 노드(index)

----------------------- 다익스트라 알고리즘 함수 -----------------------

ㄴ 시작 노드 초기화 :  최단 거리 테이블[start] = 0 & 방문 처리

ㄴ 최단 거리 테이블 distance 업데이트    # graph의 비용으로

ㄴ 최단 거리 노드 업데이트 : 방문 처리 & 연결된 다른 노드 확인 및 업데이트

ㅡㅡ 최단 거리 노드 반환 함수 호출
-----------------------------------------------------------------------------------

3. 다익스트라 알고리즘 함수 호출

4. 모든 노드로 가는 최단 거리 출력

 

방법 2. 개선된 다익스트라 알고리즘

• 시간 복잡도 : 최악의 경우에도 O(ElogV)    # V 노드의 개수, E 간선의 개수
• 간단한 다익스트라 알고리즘
  : '최단 거리가 가장 짧은 노드'를 찾기 위해, 매번 최단 거리 테이블 선형 탐색
  → O(V) 선형 시간 소요
• 개선된 다익스트라 알고리즘
  : 힙(Heap) 자료구조 사용, 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아 처리
  → O(logN) 로그 시간 소요(획기적 속도)

 

* 힙 자료구조

• 우선순위 큐 구현에 사용
• 우선순위 큐 : 우선순위가 가장 높은 데이터를 가장 먼저 삭제
  - 데이터 우선순위에 따라 처리할 때 사용
  - 파이썬에서 PriorityQueue 또는 heapq 사용 (heapq 더 빠름)
  - (가치, 물건)으로 묶어서 우선순위 큐 자료구조에 넣으면, 항상 가치 높은 물건이 먼저 나옴
• 우선순위 큐 구현시 내부적으로 최소 힙 or 최대 힙 사용
  - 최소 힙 : 값이 낮은 데이터가 먼저 삭제
  - 최대 힙 : 값이 큰 데이터가 먼저 삭제
  - 파이썬 라이브러리는 기본적으로 최소 힙 구조 이용
  - 최소 힙을 최대 힙처럼 사용하기 위해 우선순위 값에 (-) 붙여 사용(코테 자주 사용 스킬)
• 데이터 개수 N개를 넣었다가 뺄 때 → 리스트는 O(N), 힙은 O(NlogN)

우선순위 큐 구현 방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙(Heap)	O(logN)	O(logN)

 

우선순위 큐를 도입한 다익스트라 알고리즘 동작 원리

• 현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 이용

0. 출발 노드(1번 노드)를 제외한 모든 노드의 최단 거리 무한으로 설정

    우선순위 큐에 노드 정보 입력 : (거리: 0, 노드: 1)

    * 파이썬 heapq 라이브러리는 원소로 튜플 입력받으면,  첫 번째 원소를 기준으로 우선순위 큐 정렬 구성

 

1. 우선순위 큐에서 노드 꺼냄 : (0, 1)

    * 이미 처리한 적 있으면 무시, 아직 처리하지 않은 노드에 대해서만 처리

• 1번 노드에서 1번 노드까지 가는 최단거리 0
• 1번 노드를 거쳐 2, 3, 4번 노드로 가는 최소 비용 계산
• 더 짧은 경로는 각각 갱신 & 우선순위 큐에 넣기

 

 

2. 우선순위 큐에서 노드 꺼냄 : (1, 4)

• 1번 노드에서 4번 노드까지 가는 최단거리 1
• 4번 노드를 거쳐 3, 5번 노드로 가는 최소 비용 계산
• 더 짧은 경로는 각각 갱신 & 우선순위 큐에 넣기 : 3번 노드 4로 업뎃(4, 3), 5번 노드 2로 업뎃 (2, 5)

    * 이미 처리한 적 있으면 무시, 아직 처리하지 않은 노드에 대해서만 처리

 

3. 우선순위 큐에서 노드 꺼냄 : (2, 2)

• 1번 노드에서 2번 노드까지 가는 최단거리 2
• 2번 노드를 거쳐 3, 4번 노드로 가는 최소 비용 계산
• 더 짧은 경로는 각각 갱신 & 우선순위 큐에 넣기 : 없음

    * 이미 처리한 적 있으면 무시, 아직 처리하지 않은 노드에 대해서만 처리

 

4. 우선순위 큐에서 노드 꺼냄 : (2, 5)

• 1번 노드에서 5번 노드까지 가는 최단거리 2
• 5번 노드를 거쳐 3, 6번 노드로 가는 최소 비용 계산
• 더 짧은 경로는 각각 갱신 & 우선순위 큐에 넣기 : 3번 노드 3로 업뎃(3, 3), 6번 노드 4로 업뎃 (4, 6)

    * 이미 처리한 적 있으면 무시, 아직 처리하지 않은 노드에 대해서만 처리

 

5. 우선순위 큐에서 노드 꺼냄 : (3, 3)

• 1번 노드에서 3번 노드까지 가는 최단거리 3
• 3번 노드를 거쳐 2, 6번 노드로 가는 최소 비용 계산
• 더 짧은 경로는 각각 갱신 & 우선순위 큐에 넣기 : 없음

    * 이미 처리한 적 있으면 무시, 아직 처리하지 않은 노드에 대해서만 처리

 

6. 우선순위 큐에서 노드 꺼냄 : (4, 3)

• 3번 노드는 이미 처리된 적이 있으므로 무시

    * 이미 처리한 적 있으면 무시, 아직 처리하지 않은 노드에 대해서만 처리

 

7. 우선순위 큐에서 노드 꺼냄 : (4, 6)

• 1번 노드에서 6번 노드까지 가는 최단거리 4
• 6번 노드를 거쳐 2, 6번 노드로 가는 최소 비용 계산 : 연결된 노드 없음
• 더 짧은 경로는 각각 갱신 & 우선순위 큐에 넣기 : 없음

    * 이미 처리한 적 있으면 무시, 아직 처리하지 않은 노드에 대해서만 처리

 

 

8. 우선순위 큐에서 노드 꺼냄 : (5, 3)

• 3번 노드는 이미 처리된 적이 있으므로 무시

* 이미 처리한 적 있으면 무시, 아직 처리하지 않은 노드에 대해서만 처리

 

# 개선된 다익스트라 알고리즘 소스코드
import heapq
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)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [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))
    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):
    # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
    if distance[i] == INF:
        print("INFINITY")
    # 도달할 수 있는 경우, 거리를 출력
    else:
        print(distance[i])

해석

변수

: 노드의 개수 N, 간선의 개수 M, 시작 노드 start, 노드 연결 정보 graph, 최단 거리 테이블 distance, 우선순위 큐 q

 

1. 변수 입력받기

ㄴ 노드 개수N , 간선의 개수 M : map(int, input().split())

ㄴ 시작 노드 start

ㄴ 노드 연결 정보 graph : [ ] 빈 리스트로 초기화

ㄴ 최단 거리 테이블 distance : [INF] 무한으로 초기화

2. 노드 연결 정보 입력받기 : graph[a].append((b, c))

ㄴ graph[a] = (b, c)    # a → b 노드로 이동, c 비용

----------------------- 다익스트라 알고리즘 함수 -----------------------

ㄴ 우선순위 큐 q 빈 리스트로 초기화

ㄴ 시작 노드 초기화 :  heapq.heappush(q, (0, start)), distance[start] = 0

                                   # 시작 노드로 가기 위한 최단 경로 0으로 힙 삽입

ㄴ 우선순위 큐 q가 빌 때까지 반복문

ㅡㅡ q에서 최단 거리 노드 정보 꺼내기

ㅡㅡ 처리된 적 있는 노드면 무시

ㅡㅡ 인접 노드 확인 및 업데이트(q에 삽입)
-----------------------------------------------------------------------------------

3. 다익스트라 알고리즘 함수 호출

4. 모든 노드로 가는 최단 거리 출력

 

개선된 다익스트라 알고리즘의 시간 복잡도

O(ElogV)로 훨씬 빠름

• 한 번 처리된 노드는 더 이상 처리되지 않음
  = while 반복문이 노드 개수 V번 이상 반복되지 않음 & V번 반복시 최대 간선의 개수 E만큼 반복될 수 있음
• 다익스트라 최단 경로 알고리즘은 우선순위 큐 사용 유형과 흡사하므로 배워두기!

 

플로이드 워셜 알고리즘

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우

cf) 다익스트라 : 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우

 

핵심 아이디어

• 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택
• 다익스트라와 비슷하게 '거쳐 가는 노드'를 기준으로 알고리즘 수행
• 다익스트라와 다르게 최단 거리를 갖는 노드를 찾을 필요가 없음
• 노드의 개수가 N개일 때 알고리즘 상으로 N번의 단계 수행, 단계마다 O(N^2)의 연산
  → '현재 노드를 거쳐 가는' 모든 경로 고려
• 총시간 복잡도 O(N^3)
• 2차원 리스트에 '최단 거리' 정보를 저장
• 플로이드 워셜은 '다이나믹 프로그래밍'    # cf) 다익스트라는 '그리디''

 

알고리즘

• 각 단계에서 해당 노드를 거쳐 가는 경우를 고려
• 현재 확인하고 있는 노드 제외, N-1개 노드 중에서 서로 다른 노드 (A, B)쌍을 선택
• A → 1번 노드 → B 최단 거리 갱신, N-1 P 2개의 쌍을 단계마다 반복해서 확인

 

점화식

• 점화식에 따라 3중 반복문 이용하여 최단 거리 테이블 갱신
• 점화식의 의미
  'A에서 B로 가는 최소 비용'과 'A에서 K를 거쳐 B로 가는 비용' 비교하여 더 작은 값으로 갱신
  = '바로 이동하는 거리'가 '특정 노드 거쳐 이동하는 거리'보다 멀다면, 더 짧은 것으로 갱신

 

 플로이드 워셜 알고리즘 동작 원리

0. '연결된 간선'은 값을, '연결되지 않은 간선'은 무한을 넣음

    자기 자신에서 자기 자신으로 가는 비용은 0

    * 파이썬에서 무한은 int(1e9) 이용이 일반적

   

 

 

1. 1번 노드를 거쳐 가는 경우 고려 : 3P2 = 6가지 경우 고민

    D23과 D21+D13 중 더 비용이 작은 것으로 갱신

    ... 과 같은 과정을 반복하여 수행

 

 

2. 2번 노드를 거쳐 가는 경우 고려 : 3P2 = 6가지 경우 고민

    D13과 D12+D23 중 더 비용이 작은 것으로 갱신

    ... 과 같은 과정을 반복하여 수행

 

3. 3번 노드를 거쳐 가는 경우 고려 : 3P2 = 6가지 경우 고민

    D12과 D13+D32 중 더 비용이 작은 것으로 갱신

    ... 과 같은 과정을 반복하여 수행

 

4. 4번 노드를 거쳐 가는 경우 고려 : 3P2 = 6가지 경우 고민

    D12과 D14+D42 중 더 비용이 작은 것으로 갱신

    ... 과 같은 과정을 반복하여 수행

 

최종 결과

D13은 8이라는 값을 가지고 있음 = 1번 노드에서 3번 노드로 가는 최단 거리가 8이라는 의미

 

# 플로이드 워셜 알고리즘 소스코드
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] == INF:
        print("INFINITY", end=" ")
    # 도달할 수 있는 경우 거리를 출력
    else:
        print(graph[a][b]. end=" ")
print()