알고리즘 - 다익스트라

간선마다 가중치(거리,비용)가 주어진 그래프에서 최소비용으로 목적지까지 가려면 어떻게 해야할까?

그래프 탐색은 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS) 알고리즘을 통해 연결된 모든 노드를 탐색하면서 해결 할 수 있다.

그러나 연결된 노드를 지날때마다 비용이 든다면 목적지까지 이동할때의 최소비용은 어떻게 구할수 있겠는가?

출발지 A
도착지 C

	  A
(1) /   \ (5)
   B  -	 C
     (2)

가령 위 그래프에서 A에서 C로 이동할때 5원이 든다.
"A에서 C를 가는데 드는 최소 비용은 5원이구나!"

그러나 C를 가는 방법은 하나가 아니다.
A에서 B를 거쳐, C로 이동하면 1+2 = 3원이 든다.
"아, 다시보니 A에서 C를 가는데 드는 최소 비용은 3원이구나!"

따라서 A에서 B를 거쳐 C로 이동하여 지불하는 3원이 최소비용이 된다.

이처럼 목적지까지 가는데 최소비용을 알고싶다면 다익스트라 알고리즘을 사용해볼 수 있다.

---

다익스트라 알고리즘은 연결된 노드를 탐색할때마다 최소비용을 저장한다.

import sys
import math

input = sys.stdin.readline

#노드 개수 V, 간선 개수 E, 시작노드 K
V, E = map(int, input().split())
K = int(input())

graph = [[] for _ in range(V+1)]
visited = [False] * (V+1)
distance = [math.inf] * (V+1)
#각 노드들과 시작노드로부터의 거리는 무한으로 초기화한다.


for _ in range(E):
 # u에서 v로 가는 가중치 w인 간선
    u,v,w = map(int, input().split())
    graph[u].append((v,w))

def get_smallest_node():
    min_value = math.inf
    index = 0
    for i in range(1, V+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index
    # 방문하지 않은 노드중에서 시작노드와 가장 가까운 노드의 인덱스 리턴

def dijkstra(start):
    distance[start] = 0
    # 시작노드와 시작노드의 거리는 0이다
    visited[start] = True
    # 시작노드를 방문처리한다.
    
    for j in graph[start]:
        distance[j[0]] = j[1]
        # 시작 노드와 연결된 노드들과의 거리를 저장

	#최단 거리인 노드부터 탐색
    for _ in range(V - 1): # 시작노드를 제외한 모든 노드들의 갯수만큼 반복
        now = get_smallest_node()
        visited[now] = True
        
        for i in graph[now]:
            cost = distance[now] + i[1]
            # cost = now노드와 시작노드까지의 거리 + now노드와 연결된 노드 사이의 거리
            
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                # now노드와 연결된 노드부터 시작노드 사이의 거리 = distance[i[0]]
                # 최단거리 찾으면 갱신
                
dijkstra(K)

for i in range(1, V+1):
    if distance[i] == math.inf:
        print('INF')
    else:
        print(distance[i])

입력
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

출력
0
2
3
7
INF

위 방법의 시간복잡도는 O($V^2$)이다.

---

함수를 통해 현재노드와 시작노드의 최단거리를 하나씩 찾는 대신

우선순위 큐, heap을 이용하면 시간복잡도를 줄일 수 있다.

import sys
import math
import heapq

input = sys.stdin.readline

#노드 개수 V, 간선 개수 E, 시작노드 K
V, E = map(int, input().split())
K = int(input())

graph = [[] for _ in range(V+1)]
visited = [False] * (V+1)
distance = [math.inf] * (V+1)


for _ in range(E):
    u,v,w = map(int, input().split())
    graph[u].append((v,w))

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(K)

for i in range(1, V+1):
    if distance[i] == math.inf:
        print('INF')
    else:
        print(distance[i])

위 방법의 시간복잡도는 O($E*logV$)이다.