Bellman Ford's와 다익스트라(Dijkstra) 알고리즘 - 2

이전 Bellman Ford알고리즘에 이어서 포스팅합니다 :)

이번에도 이전 포스트와 마찬가지로 백준 1916번 문제를 예시로 포스팅합니다.

노드는 총 5개(N), 그리고 이동할 수 있는 간선의 갯수는 총 8개(M)입니다. 이때 그래프를 그려보면 아래와 같이 그릴 수 있습니다.

위 그래프를 기반으로 다익스트라 알고리즘을 사용해서 문제를 해결해보도록 하겠습니다.

우선 다익스트라(Dijkstra)알고리즘은 우선순위 큐를 이용해 구현합니다. Python에서는 heap을 통해 구현한다고 하여 from heapq import heappush, heappop를 사용하였습니다.

기초 작업은 이전 포스트에서 다루었던 벨만포드 방식과 같게 처리하였습니다. 시작지점을 제외한 모든 nodeState[]에 INF로 초기화해주었습니다.

진행될 프로세스

1) 우선순위 큐에 [시작지점, 가중치] push
2) while문
2-1) front pop
2-2) front(가중치)와 기존에 저장되있던 nodeStates(노드)와 비교
2-3) graph에서 갈 수 있는 노드들 비교 후, queue에 push

그 후에 우선순위 큐를 이용하여 구현하였는데, 그림으로 표현하면 아래와 같습니다.

0의 가중치를 가진 1번 노드의 모습입니다.

while 문 안에서 front에 위치한 노드를 pop한 후에 갈 수 있는 노드들을 push해줍니다. 이때 push하기 전에 먼저 nodeStates 리스트에 해당하는 index에 맞춰 값을 update 해줍니다.

위 그림처럼 모두 push가 완료된 상태의 nodeStates는 다음과 같습니다.

nodeState = [0, 0, 2, 3, 1, 10]

그리고 우선순위 큐에 저장된 모습은 다음과 같습니다.

priorityQueue = [[2,2], [3,3], [4,1], [5,10]]

다음 단계를 그림으로 보여드리면 다음과 같습니다.

[2,2]가 pop 이 되고 우선순위 큐에 맞게 배치가 된다음 2번노드에서 4번노드로 갈 수 있어 가중치 비교를 해보았을 때 False가 나오게 됩니다. 따라서 새롭게 push 를 하지않고 또 front를 pop합니다.

위 그림처럼 [3,3]이 pop 이 되고 나서 갈 수 있는 노드로 update 작업을 해줄 때, update된 5번 노드의 가중치가 우선순위 큐에 새롭게 push 됩니다.

다음과정에서 [4,1], [5,4], [5,10]이 차례대로 pop 이 되면서 while문이 종료됩니다.

전체 코드를 보면 아래와 같습니다.

import sys
# dijkstra algorithm
from heapq import heappush, heappop
# input
N = int(sys.stdin.readline().rstrip())
M = int(sys.stdin.readline().rstrip())
# N nodes graph
graph = [[] for _ in range(N + 1)]
for i in range(M):
    start, dest, weight = map(int, sys.stdin.readline().split())
    graph[start].append({'dest': dest, 'weight': weight})
# src, dest
beginPoint, endPoint = map(int, sys.stdin.readline().split())

# Bellman Ford's Algorithm
nodeStates= [0] * (N + 1)   # [0] no use
INF = 10000000001
# 1) set other nodes
for i in range(1, N + 1):
    if i != beginPoint: nodeStates[i] = INF
# 2) update node
# start from beginPoint
# using priority queue
priorityQueue = []
# p_queue, [ node, weight ]
heappush(priorityQueue, [beginPoint, 0])
while priorityQueue:
    n, w = heappop(priorityQueue)
    print(priorityQueue)
    if nodeStates[n] < w: continue
    for bus in graph[n]:
        weighted = w + bus['weight']
        if nodeStates[bus['dest']] > weighted:
            nodeStates[bus['dest']] = weighted
            heappush(priorityQueue, [bus['dest'], weighted])
print(nodeStates[endPoint])

BFS 방식과 비슷한 방식으로 코드를 작성했습니다.