[알고리즘] 최단 경로 알고리즘(1) - 다익스트라(Dijkstra) 알고리즘

최단 경로 알고리즘이란, 주어진 노드와 간선(edge)들 중, 가장 짧은 경로를 찾는 알고리즘입니다.

즉, 서울에서 인천, 대전, 광주, 부산을 갈 수 있는 가장 짧은 경로를 찾는 것입니다.

 

0. 최단 경로 문제

- 다익스트라 알고리즘 이용(BFS 너비 우선 탐색)

- "우선 순위 큐( 최소 힙 방식)"을 이용하여, 시간 복잡도 O(nlogn)

- 이동경로가 양수라 하면 Dijkstra 알고리즘, 음수를 포함한다면 Bellman-ford 알고리즘 사용!

 

* 다익스트라 알고리즘

 

1. 출발 노드를 설정

2. 최단 거리 테이블을 초기화(그러므로 최단 거리를 기록할 테이블을 정의해야 함)

3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택(방문하지 않은 노드를 체크해야 하므로 이를 위한 테이블을 정의해야 함)

4. 해당 노드를 거쳐 다른 노드로 가는 간선 비용을 계산하여 최단 거리 테이블을 업데이트

5. 위 과정에서 3, 4번을 반복

 

[풀이]

- 2가지 빈 리스트 필요(최단거리 기록 테이블 리스트, 방문 노드 체크 리스트)

- 두 리스트 모두 노드가 N개 있다고 할 때, N+1크기로 정의하기

- 최단거리 기록 테이블은 큰 수로 초기화(1억 1e8)

- 방문 체크 리스트는 False(방문하지 않음)으로 초기

 

[자세히]

1. 사직노드를 1번이라 하면 노드번호 1번의 거리는 0으로 업뎃

2. 시작노드 1번과 인접한 노드(2, 3, 4)에 접근 후 거리 업뎃

3. 시작노드였던 1번 노드를 방문 처리 하고, 1번 노드의 인접노드들(2, 3, 4) 중 방문하지 않은 노드(2, 3, 4)중 시작노드인

1번 노드와 가장 최단거리인 4번 노드를 다음에 탐색할 노드(4번!)로 선택! min( , )

4. 다음 탐색할 노드인 4번 노드에 인접한 노드 찾기(3, 5)

5. 3번 노드는 이전에 1번 노드와 인접한 노드이므로 min(1번노드와 거리, 1과 4의 거리+ 4와 3의 거리) 으로 업뎃

6. 5번 노드는 min(기본값인 무한대, 1과 4의 거리 + 4와 5의 거리) 로 업뎃

7. 반복

8. 가장 마지막으로 갱신된 거리 테이블을 기준으로 방문하지 않은 노드들 중 가장 거리가 작은

즉, 원소값이 가장 작은 인덱스 번호를 다음으로 탐색할 노드로 선정

9. 방문하지 않은 노드 중 갱신한 테이블 기준으로 시작노드와 가장 최단거리인 노드를 탐색한다.

 

 

[핵심]

- 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택하는 과정 반복

 

[구현]

 

1) 기본(비효율적)

# 다익스트라 가장 기본적인 구현(시간 오래걸림_비효율적)
import sys

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

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

# 주어진 그리프 정보를 담는 N개 길이의 리스트
graph = [[] for _ in range(n+1)]

# 방문 처리 리스트
visited = [[False] * (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): # n개 노드
        if not visited[i] and distance[i] < min_value: # 방문하지 않았고, 거리가 무한보다 작은 경우
            min_value = distance[i] # 작은 값으로 업뎃(인덱스 = 0 인 상태)
            index = i # 인덱스 증가 (인덱스 0부터~)
    return index



# 다익스트라 알고리즘
def dijkstra(start):
    # 시작노드 -> 시작노드 거리 계산 및 방문처리
    distance[start] = 0
    visited[start] = True
    # 시작노드의 인접한 노드들에 대해 최단거리 계산
    for i in graph[start]: # graph[0] = (b, c) 꼴
        distance[i[0]] = i[1] # distance[도착노드] = 거리값

    # 시작 노드 제외한 n-1개의 다른 노드들 처리
    for _ in range(n-1):
        now = get_smallest_node() # 방문하지 않은 노드이면서 시작노드와 최단 거리 노드 반환
        visited[now] = True # 방문 처리

        # 해당 노드의 인접한 노드들 간의 거리 계산
        for next in graph[now]:
            cost = distance[now] + next[1] # (시작 -> now거리) + (now -> now의 인접노드 거리)
            if cost < distance[next[0]]: # cost < 시작에서 now의 인접노드 다이렉트 거리
                distance[next[0]] = cost # 작은 값으로 업뎃

# 다익스트라
dijkstra(start)

# 출력
for i in range(1, n+1): # n개
    if distance[i] == INF: # 거리가 무한대 (업뎃이 안 된 경우)
        print('도달 할 수 없음')
    else:
        print(distance[i]) # 최단거리 출력

 

2) 우선순위 큐 이용

import sys
import heapq

input = sys.stdin.readline
n, m = map(int, input().split())

start = int(input())
INF = int(1e9)

# 그래프 생성
distance = [INF] * (n+1)
graph = [[] for _ in range(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, node = heapq.heappop(q)

        # 큐에서 뽑아낸 거리가 이미 갱신된 거리보다 클 경우(=방문한 셈) 무시
        if distance[node] < dist:
            continue

        # 큐에서 뽑아낸 노드와 연결된 인접노드들 탐색
        for next in graph[node]:
            cost = distance[node] + next[1]   # (시작 -> node거리) + (node -> node의 인접노드 거리)
            if cost < distance[next[0]]:      # cost < 시작 -> node의 인접노드 거리
                distance[next[0]] = cost # 작은 걸로 업뎃
                heapq.heappush(q, (cost, next[0]))

# 다익스트라
dijkstra(start)

# 출력
for i in range(1, len(distance)):
    if distance[i] == INF:
        print('도달할 수 없음')
    else:
        print(distance[i])

 

[입력]

6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
4 3 3
4 5 1
5 3 1
5 6 2
5 3 5

[출력]

0
2
3
1
2
4