다익스트라

목적

시작노드에서 각 노드까지 최단거리를 구하는 알고리즘

O(ElogV)의 시간 복잡도를 갖는다

우선순위 큐로 거리가 짧은 노드를 우선적으로 탐색한다

BFS는 가중치가 같은(없는) 그래프에서, 다익스트라는 가중치가 서로 다른 그래프에서 사용한다

 

 

코드

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, len(distance)):
    if distance[i]==INF:
        print('INF')
    else:
        print(distance[i])

 

 

설명

n은 노드의 갯수, m은 간선의 갯수를 받는다

 

start는 시작 노드의 번호를 받는다

 

distance에는 시작노드부터 목적노드각 인덱스까지의 최단 거리를 담는다

 

graph에는 연결돼있는 노드와 가중치가 담긴다

a노드(인덱스)와 b노드가 가중치 c로 연결돼있다는 정보가 담긴다.

 

q에는 탐색할 노드 번호와 가중치를 담는다.

heapq는 첫번째 인자가 가장 정렬 우선순위가 높으므로 가중치를 첫번째 인자로 선정한다.

이렇게 하면 가중치가 짧은 노드들을 먼저 탐색하고 가중치가 긴 노드들은 23~24번째 줄에서 대부분 걸러지게 해서 시간복잡도를 줄여준다

 

23번째줄에 if distance[now] <= dist 을 붙이면 안 되는지 시도해봤는데 =을 붙이게 되면 시작노드가 continue에 걸려 돌지 않게 돼서 <를 사용하는 것으로 보인다.

 

25~29번째 줄에서 탐색할 노드를 BFS식으로 탐색하며 현재 노드를 거쳐 다른 노드로 이동하는 거리가 distance 배열에 담겨있는 값보다 더 짧은 경우 distance 배열 및 탐색할 (거리, 노드)를 담는 q를 갱신하게 된다

 

 

 

예시

1.

distance 배열

노드	1	2	3	4
거리	0	INF	INF	INF

q=[(0, 1)]

처음 19~20번째 코드에 의해 distance[1]의 값이 0으로 초기화되고 q에 (0, 1)의 값이 담긴다

 

 

2.

노드	1	2	3	4
거리	0	6	2	INF

q=[(2, 3), (6, 2)]

 

노드 1과 연결돼있는 노드 2, 3의 최단거리 값이 갱신된다

 

 

3.

노드	1	2	3	4
거리	0	5	2	7

q=[(5, 2), (6, 2), (7, 4)]

노드 3과 연결돼 있는 노드 4, 노드 3의 최단거리값이 갱신된다

 

 

4.

노드	1	2	3	4
거리	0	5	2	6

q=[(6, 2), (6, 4), (7, 4)]

 

 

5. 

노드	1	2	3	4
거리	0	5	2	6

q=[(7, 4)]

 

(6, 2)의 값은 23~24번째 줄에서 걸러지게 되는데 (6, 4)의 값은 23번째 줄의 부등호가 < 이기 때문에 탐색을 진행하게 된다

 

 

6.

노드	1	2	3	4
거리	0	5	2	6

q=[]

(7, 4)의 값은 23~24번째 줄에서 걸러지게 된다

21번째 줄에 의해 q가 비었으므로 while 문이 종료된다

 

 

소감

다시 볼때마다 새로워서,,, 자세히 포스팅해보았다.