다익 스트라 알고리즘 공부하기

• https://www.fun-coding.org/Chapter20-shortest-live.html 자료를 보면서 공부하였습니다.

1. 최단 경로 문제란?

• 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제
• 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적

최단 경로 문제 종류

1. 단일 출발 및 단일 도착 최단 경로 문제
   • 그래프 내의 특정 노드 u에서 출발, 또다른 특정 노드 v에 도착하는 가장 짧은 경로를 찾는 문제
2. 단일 출발 최단 경로 문제
   • 그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제
3. 전체 쌍 최단 경로
   • 그래프 내의 모든 노드 쌍(u, v)에 대한 최단 경로를 찾는 문제

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

• 다익스트라 알고리즘은 위 종류 중 2번에 해당되고 하나의 정점에서 다른 모든 정점 간의 각각 가장 잛은 거리를 구하는 문제

다익스트라 알고리즘 로직

• 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법
• 다익스트라 알고리즘은 너비우선탐색과 유사
  - 첫 정점부터 각 노드 간의 거리를 저장하는 배열을 만든 후, 첫 정점의 인접 노드간의 거리부터 먼저 계산하면서, 첫 정점부터 해당 노드간의 가장 짧은 거리를 해당 배열에 업데이트
• 우선순위 큐를 활용한 알고리즘
  - 우선순위 큐는 MinHeap 방식을 활용해서, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내게 됨
  1) 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장
  • 초기에는 첫 정점의 거리는 0, 나머지는 무한대로 저장함
  • 우선순위 큐에 (첫 정점, 거리 0)만 먼저 넣음
  2) 우선순위 큐에서 노드를 꺼냄
  • 처음에는 첫 정점만 저장되어 있으므로, 첫 정점이 꺼내짐
  • 첫 정점에 인접한 노드들 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 정점에서 각 정점까지의 거리를 비교한다.
  • 배열에 저장되어 있는 거리보다, 첫 정점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트 한다.
  • 배열에 해당 노드의 거리가 업데이트 된 경우, 우선순위 큐에 넣는다.
    • 결과적으로 너비 우선 탐색 방식과 유사하게, 첫 정점에 인접한 노드들을 순차적으로 방문하게 됨
    • 만약 배열에 기록된 현재까지 발견된 가장 짧은 거리보다, 더 긴거리를 가진 노드 및 거리의 경우에는 해당 노드와 인접한 노드간의 거리 계산을 하지 않음
  3) 2번의 과정을 우선순위 큐에 꺼낼 노드가 없을 때까지 반복한다.

3. 다익스트라 알고리즘 파이썬 구현하기

우선순위 큐 예시

import heapq

queue = []

heapq.heappush(queue, [2, 'A'])
heapq.heappush(queue, [5, 'B'])
heapq.heappush(queue, [1, 'C'])
heapq.heappush(queue, [7, 'D'])

for i in range(len(queue)):
	print(heapq.heappop(queue))

결과
[1, 'C']
[2, 'A']
[5, 'B']
[7, 'D']

다양한 다익스트라 알고리즘

mygraph = {
	'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5},
}

import heapq

def dijkstra(graph, start):
	distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = []
    heapq.heappush(queue, [distances[start], start])
    
    while queue:
    	current_distance, current_node = heapq.heappop(queue)
        if distances[current_node] < current_distance:
        	continue
        for adjacent, weight in graph[current_node].items():
        	distance = current_distance + weight
            
            if distance < distances[adjacent]:
            	distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])
     return distances  

import heapq
import sys

def dijkstra(start):
	# 초기 배열 설정
    distances = {node: sys.maxsize for node in graph}
    # 시작 노드의 거리는 0으로 설정
    distances[start] = 0
    queue = []
    heapq.heappush(queue, (distances[start], start))
    
    # 우선 순위 큐에 데이터가 하나도 없을 때까지 반복
    whild queue:
    	# 가장 낮은 거리를 가진 노드와 거리를 추출
        current_distance, node = heapq.heappop(queue)
        if distances[node] < current_distance:
        	continue
            
        # 대상인 노드에서 인접한 노드와 거리를 순회
        for adjacency_node, distance in graph[node].items():
        	# 현재 노드에서 인접한 노드를 지나갈 때까지의 거리를 더함
            weighted_distance = current_distance + distance
            # 배열의 저장된 거리보다 위의 가중치가 더 작으면 해당 노드의 거리 변경
            if weighted_distance < distances[adjaceney_node]:
            	# 배열에 저장된 거리보다 가중치가 더 작으므로 변경
                distances[adjacency_node] = weighted_distance
                # 다음 인접 거리를 계산하기 위해 우선 순위 큐에 삽입(노드가 동일해도 다 저장)
     return distances

graph = {
	'A': {'B': 10, 'C': 3},
    'B': {'C': 1, 'D': 2},
    'C': {'B': 4, 'D': 8, 'E': 2},
    'D': {'E': 7},
    'E': {'D': 9},
}

result = dijkstra('A')
print(result)

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 = dist + next[1]
            # cost < 시작->node의 인접노드 거리
            if cost < distance[next[0]]:
            	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])