[Algorithm 개념] 다익스트라 알고리즘 (최단거리)

최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미.

1. 다양한 문제 상황

1) 한 지점에서 다른 한 지점까지의 최단경로

2) 한 지점에서 다른 모든 지점까지의 최단경로

3) 모든 지점에서 다른 모든 지점까지의 최단경로

- 각 지점은 그래프에서 노드로 표현.

- 지점 간 연결된 도로는 그래프에서 간선으로 표현.

 

2. 알고리즘 동작 과정

1. 출발 노드를 설정.

2. 최단거리 테이블을 초기화.

3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 (weight)를 선택.

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다.

But! 총 O(V)번에 걸쳐서 최단거리가 가장 짧은 노드를 매법 선형 탐색해야 한다. 따라서 전체 시간 복잡도는 O(V2) 이다.

일반적으로 코딩 테스트의 최단 경로 문제에서 전체 노드의 개수가 5000개 이하라면 이 코드로 문제를 해결할 수 있다. 하지만 10,000개를 넘어가는 문제라면 힘듬! 

 

3.  자료구조 종류

1. 스택 (Stack) : 가장 나중에 삽입된 데이터 (DFS)

2. 큐 (Queue) : 가장 먼저 삽입된 데이터 (BFS)

3. 우선순위 큐 (Priority Queue) : 가장 우선순위가 높은 데이터 (Dijkstra)

 

⭐️ 우선 순위 큐 (priority queue)

- 우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

- 예를들면 여러개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 한느 경우에 우선순위 큐를 이용할 수 있음.

 

힙(Heap)

우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나. 최소힙(min heap)과 최대힙(max heap)이 있다. 

#최소힙
import heapq

def heapsort(iterable):
    h = []
    result = []
    #모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)
        
    #힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result

result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)

#최대힙
import heapq

#내림차순 힙 정렬
def heapsort(iterable):
	h = []
    result = []
    
    #모든 원소를 차례대로 힙에 삽입
    for value in iterable:
    	heapq.heappush(h, -value)
        
    #힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
    	result.append(-heapq.heappop(h))
    return result
    
result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result) #[9,8,7,6,5,4,3,2,1,0]

 

다익스트라 알고리즘 : 개선된 구현 방법

단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 힙 자료구조를 이용. 다익스트라 알고리즘이 동작하는 기본 원리는 동일.

• 현재 가장 가까운 노드를 저장해 놓기 위해서 힙 자료구조를 추가적으로 이용한다는 점이 다름.
• 현재의 최단 거리가 가장 짧은 노드를 선택해야 하므로 최소 힙을 사용해야함.
• 시간 복잡도 : O(ElogV)
• 직관적으로 전체과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사.

import heapq
import sys

input = sys.stdin.readline
INF = int(1e9)
#노드, 간선 입력 받기
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()) #시작노드, 도착노드, 가중치
    graph[a].append((b,c))
    
def dijkstra(start):
	q = []
    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):
	if distance[i] == INF:
    	print("INF")
    else:
    	print(distance[i])