WEEK03 - TIL 다익스트라

다익스트라(Dijkstra) 알고리즘이란?

1. 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘

2. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. [but, 음수일 땐 사용 불가능]

3. 다익스트라는 다이나믹 프로그래밍 or 그리디 알고리즘으로 분류되기도 한다.

= 최단 거리는 여러 개의 최단 거리로 이루어져있기 때문이다. [작은 문제가 큰 문제에 속해있는 다이나믹 유형]

4. 기본적으로 하나의 최단 거리를 구할 때 이전까지 구했던 최단 거리 정보를 그대로 사용

5. 다익스트라는 정렬 사용 - 정렬 이후에 가장 적은 것을 하나씩 선택하는 게 알고리즘에 포함 [그리디 알고리즘]

 

다익스트라 작동 과정

1. 출발 노드를 설정

2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장

3. 방문하지 않은 노드 중에 가장 비용이 적은 노드를 선택

4. (가장 비용이 적은 노드를 선택)해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려해 최소 비용을 갱신

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

 

ex)

 

출발 = 1 [방문한 곳 노란색]

0

2

5

1

∞

∞

= 제일 최소 비용인 4번 노드(1)를 선택 // 현재 최소 비용: 0 → 1을 받음

 

다음 노드 선택 = 4

0

2

5 → 4

1

∞ → 2

∞

= 4번을 선택했을 때 3번 노드까지의 최소 비용이 1+3=4이므로 최소 비용을 갱신해준다.

= 4번 기준 5번으로 가는 최소비용은 1+1=2이므로 최소 비용 저장해준다.

= 최소 비용이 2번(2)과 5번 노드(2)인데, 이럴 경우 더 앞에 있는 노드(2번 노드)를 선택해준다.

 

다음 노드 선택 = 2

0

2

4

1

2

∞

= 2번 노드랑 이어진 게 3번 노드인데, 최소 비용보다 크니까, 최소 비용 갱신은 없음!

= 그래서 다음 최소 비용인 5번 노드로 간다

 

다음 노드 선택 = 5

0

2

4 → 3

1

2

∞ → 4

= 3까지 가는 최소 비용은 1+1+1=3이므로 3으로 갱신

= 5번 노드에서 6번 노드로 이어져 있으니, 5에서 6으로 가는 비용이 1+1+2=4로 저장해준다.

= 다음 최소 비용인 3번 노드로 간다

 

다음 노드 선택 = 3

0

2

3

1

2

4

= 3 기준에서 6으로 가는 최소 비용에는 갱신이 이루어지지 않으므로 갱신은 없다.

= 남은 6번 노드로 고고

 

다음 노드 선택 = 6

0

2

3

1

2

4

 

 

다익스트라 기본적인 구현 방법

- 단계마다 방문하지 않은 노드 중 최단 거리가 짧은 노드를 선택하기 위해 매 단계마다 1차원 테이블의 모든 원소를 확인(순차 탐색)한다.

import sys
input = sys.stdin.readline
INF = int(1e9) #초기화 할 때 무한값을 넣어야함 // 10억

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())
    # 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 not visited[i] and distance[i] < min_value:
            min_value = distance[i]
            index = i
    return index

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

    # 시작노드 제외한 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):
    if distance[i] == INF:
        print('도달 할 수 없음')
    # 도달 가능 거리 출력
    else:
        print(distance[i])

 

다익스트라는~

- 최소 비용을 단순히 선형 탐색으로  찾도록 했기 때문에, 시간 복잡도가 O(N²)으로 형성된다.

- 최대한 빠르게 작동시켜야 하는 경우엔 힙 구조를 활용해 시복을 O(NlogN)으로 만들 수 있다.

- 정점의 개수가 많은데, 간선은 적을 때 굉장히 비효율적으로 작동한다.

 

---

다익스트라 알고리즘과 기본원리는 동일한데,

+ 현재 가장 가까운 노드를 저장해 놓기 위해 힙을 추가로 이용한다는 것이 다르다.

+ 가장 짧은 노드를 선택해야 해서 최소힙을 사용

 

 

우선순위 큐를 이용한 구현 방법

from collections import defaultdict
import sys
import heapq
INF = int(1e9)

input = sys.stdin.readline

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

start = int(input())
distance = [INF] * (n+1)

graph = defaultdict(list)
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))  # 시작노드 정보 우선순위 큐에 삽입 / 최단경로는 0으로 설정
    distance[start] = 0            # 시작노드->시작노드 거리 기록
    while q:
        dist, now = heapq.heappop(q)
        # 큐에서 뽑아낸 거리가 이미 갱신된 거리보다 클 경우(=방문한 셈) 무시
        if distance[now] < dist:
            continue
        # 큐에서 뽑아낸 노드와 연결된 인접노드들 탐색
        for next in graph[now]:
            cost = dist + next[1]   # 시작->now거리 + now->now의인접노드 거리
            if cost < distance[next[0]]:      # cost < 시작->now의인접노드 거리
                distance[next[0]] = cost
                heapq.heappush(q, (cost, next[0]))


dijkstra(start)

# 바뀌는 부분
for i in range(1, n+1):
    if distance[i] == INF:
        print('도달할 수 없음')
    else:
        print(distance[i])