[Week03] 다익스트라 알고리즘의 이해

 

import sys
import heapq

input_value = sys.stdin.read().splitlines()

arr = []

# 도시 갯수
N = int(input_value[0])

# 버스 갯수
M = int(input_value[1])

start, end = map(int, list(input_value[-1:][0].split()))

graph = [[] for _ in range(N + 1)]

for i in input_value[2:-1]:
    a, b, weight = map(int, i.split())
    graph[a].append([b, weight])

def dijkstra(graph, start):
    distance = {node : float('inf') for node in range(len(graph))}
    distance[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        cur_dist, cur_node = heapq.heappop(priority_queue)
        
        if cur_dist > distance[cur_node]:
            continue

        for node, w in graph[cur_node]:
            dist = cur_dist + w
            if dist < distance[node]:
                distance[node] = dist
                heapq.heappush(priority_queue, (dist, node))
    return distance
    
print(dijkstra(graph=graph, start=start)[end])

 

다익스트라 알고리즘

 

간선에 거리가 있을 때 목적지에서 도착지까지 최소의 거리를 가지고 가는 경로를 구하기 or 최소 거리 구하기

 

1. 거리에 대한 배열 선언 : minimum 비교로 inf값을 가지는 배열 선언

2. 시작은 거리가 0이니 0으로 선언 후 시작

3. 우선 순위 큐에 거리와 현재 node를 입력할 수 있도록 init

4. 우선 순위 큐에 들어 있는 거리와 node를 pop하여 비우고, 현재 거리와 node로 씀

5. 거리가 현재 노드보다 크다? -> start 노드가 아닌걸로 판단하여 continue

6. 그래프에 있는 거리와 node를 가지고 연산 진행

 

그래프는 머리 아픈거 같다 히히..