다익스트라(dijkstra) ✔

이론 ✌

• 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미
• 문제의 예시로
  • 한 지점에서 다른 한 지점까지의 최단 경로
  • 한 지점에서 다른 모든 지점까지의 최단 경로 <- 다익스트라
  • 모든 지점에서 다른 모든 지점까지의 최단 경로

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

• 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단경로를 계산
• 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상 작동
• 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류됨
  • 매 상황에서 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복

---

동작과정 🏆

1️. 출발 노드를 설정 2️. 최단 거리 테이블을 초기화 3️. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택

1. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
2. 위 과정에서 3, 4번을 반복

---

• 초기상태에서 출발노드는 최단 거리가 0이므로 최단 거리 테이블에서 0으로 하고 나머지들은 아직 탐색을 하지 않았고 모르니깐 무한으로 초기화

• 최단거리 테이블에서 거리가 가장 짧고 방문하지 않은 1번 노드를 처리하는데 1번 노드와 인접한 2, 3, 4번 노드는 이제 거리를 알 수 있으니깐 최단 거리 테이블을 갱신해줘야함 -맨 처음에는 무한으로 되어 있다가 현재 1번 노드를 거쳐서 2, 3, 4노드에 도착하는 거리가 더 짧으니깐 갱신을 해줘야함

• 그 다음 단계에서 이제 최단 거리 테이블에서 방문 하지 않은 노드 중 가장 짧은 거리인 노드를 선택해야 함 -> 4번 노드 선택

• 최단 거리 테이블을 갱신해줘야 하는데 이전 스텝과 마찬가지로 인접한 노드들 중에 현재 노드(4번)을 거쳐갈 때의 거리가 더 짧으면 최단 거리 테이블을 갱신해줌

• 1번은 이전에 처리가 되어서 더 이상 작은 값이 나올 수가 없음
• 마찬가지로 4번은 이번 단계 이후로 부터 값이 절대 안바뀜 왜냐하면 1번(출발노드)에서 가장 짧은 거리를 선택해서 뽑은거니깐

• 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 2번을 처리
• 2번과 인접한 노드가 3, 4 가 잇는데 둘 다 2번을 거쳐서 도착하는게 기존의 최단거리보다 더 크기 때문에 갱신 x

---

다익스트라 알고리즘의 특징 🔥

1. 그리디 알고리즘 : 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복
2. 단계를 거치며 한 번 처리된 노드의 최단거리는 고정 되어 더 이상 바뀌지 않음
   • 따라서 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것

다익스트라 알고리즘 코드 (간단 구현) 📃

import sys
input = sys.stdin.readline
INF = int(1e9) #무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
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 distance[i] < min_value and not visited[i]:
      min_value = distance[i]
      index = i
  return index

def dijkstra(start):
  # 시작 노드에 대해서 초기화
  visited[start] = True
  distance[start] = 0
  
  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[j[0]]:
        distance[j[0]] = cost


dijkstra(start)

# start에서 다른 노드로 가기 위한 최단 거리 출력
for i in range(1, n+1):
  # 도달할 수 없는 경우, -1 출력
  if distance[i] == INF:
    print(-1)
  else:
    print(distance[i])

• 이 방식은 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 최단 거리 테이블의 모든 원소를 순차 탐색함..

---

힙 자료구조를 이용한 다익스트라 알고리즘 코드 📃

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) #무한을 의미하는 값으로 10억을 설정

# 노드의 개수, 간선의 개수를 입력받기
n, m = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for _ 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)
    # 현재 노드가 이미 처리된 적이 있는 노드라면 무시
    # 이전에 처리되었다면 해당 노드가 최단 거리를 기록했을 것임
    # 그래서 최단거리를 기록하는 배열 distance에서 해당 노드 값보다
    # 지금 꺼내본 거리가 더 크다면 볼 필요도 없는 것
    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)

# start에서 다른 노드로 가기 위한 최단 거리 출력
for i in range(1, n+1):
  # 도달할 수 없는 경우, -1 출력
  if distance[i] == INF:
    print(-1)
  else:
    print(distance[i])

---

개선된 구현 방법(힙 자료구조 이용) 성능 분석 ❗

• 힙 자료구조를 이용하는 다익스트라 알고리즘의 시간 복잡도는 O(ElogV)이다.
• 왜냐하면 위 코드의 dijkstra 함수의 while문은 노드를 하나씩 꺼내서 검사하는 건데 이때 이미 처리된 적이 있는 노드라면 무시하는 성격 때문에 노드의 개수 V 이상의 횟수로는 처리가 되지 않는다.
  • 결과적으로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 최대 간선의 개수(E)만큼 연산이 수행됨
• 결국 시간 복잡도를 O(ElogE)
• 중복 간선을 포함하지 않는 경우에 이를 O(ElogV)로 정리할 수 있음

---

[이것이 취업을 위한 코딩테스트다 with 파이썬] - 나동빈 님 유튜브를 보고 자료는 캡처, 정리는 나동빈 해설 + 나만의 언어로 표현했슴다.

---