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])
Author And Source
이 문제에 관하여(Bellman Ford's와 다익스트라(Dijkstra) 알고리즘 - 1), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@seunghwanly/Bellman-Fords와-다익스트라Dijkstra-알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)