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

Bellman Ford's 와 다익스트라(Dijkstra) 알고리즘을 접하게 된 건 다름이 아니라 백준 1916번 문제를 풀다가 알게되었는데 정리해두면 좋을 거 같아서 포스팅하게 되었습니다 :)

문제로 바로가기 👉

먼저 제가 구현한 코드와 Bellman Ford's 알고리즘을 보여드리도록 하겠습니다. Python을 근래에 시작해서 유익한 코드가 아닐 수 있지만 원리만 이해할 수 있도록 작성해보았습니다.

Bellman Ford(벨만포드) 알고리즘

예시와 함께 그림을 그려보았습니다.
주어진 노드의 갯수는 5개이며 각 노드는 번호로 구성이 되어있고 시작지점이 1인 아래 그림과 같이 주어졌다고 가정을 해보면,

이렇게 생긴 그래프를 그릴 수 있습니다.

1) 먼저 시작지점을 제외한 나머지 노드들의 값을 무한대로 초기화해줍니다.

초기화를 하게되면 다음과 같은 그림이 나옵니다.
2) 시작지점을 시작으로 시작지점에서 다른 노드로 갈 수 있는 노드들을 업데이트 해줍니다.

예를 들어서 1번에서 2번으로 갈 경우에는 weight가 2입니다. 시작지점은 값이 0이라고 가정하고 있기 때문에 0+2 < 무한이므로 2번 노드의 값은 2가 됩니다.

이때 1번 노드(시작지점)에서 다른 노드로 갈 수 있는 경우 모두 같은 작업을 진행해줍니다.

3) 시작지점 이외에 다른 노드에서도 업데이트 작업을 똑같이 진행해줍니다.

2번 노드에서 진행한 모습

3번 노드에서 진행한 모습
3 → 4 경우에는 기존에 있던 값10이 새로 연산된 3+1보다 크기 때문에 4의 값을 업데이트해주었습니다.

이런 방식으로 진행하면 아래와 같이 코드를 작성할 수 있습니다.

# 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

먼저 nodeStates란 리스트안에 N+1만큼의 원소를 만들어주었습니다. (1부터 시작해서 N+1만큼 생성했습니다.)
다음에는 시작지점을 제외한 나머지 노드를 INF로 초기화해주었습니다.

# 2) update node
for bus in graph[beginPoint]:
    weighted = nodeStates[beginPoint] + bus['weight']
    if nodeStates[bus['dest']] > weighted: nodeStates[bus['dest']] = weighted

생성한 그래프에서 시작지점부터 갈 수 있는 노드들을 업데이트 해주는 코드입니다. 그림보기

# update others
for i in range(1, N+1):
    if i != beginPoint:
        for bus in graph[i]:
            weighted = nodeStates[i] + bus['weight']
            if nodeStates[bus['dest']] > weighted: nodeStates[bus['dest']] = weighted

마지막으로 나머지 노드를 업데이트해주는 코드입니다.

import sys
# 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
for bus in graph[beginPoint]:
  weighted = nodeStates[beginPoint] + bus['weight']
  if nodeStates[bus['dest']] > weighted: nodeStates[bus['dest']] = weighted
# update others
for i in range(1, N+1):
  if i != beginPoint:
      for bus in graph[i]:
          weighted = nodeStates[i] + bus['weight']
          if nodeStates[bus['dest']] > weighted: nodeStates[bus['dest']] = weighted

print(nodeStates[endPoint])

다익스트라 포스트 보러가기 👉