[알고리즘][파이썬] 벨만-포드 알고리즘
💡 벨만-포드 알고리즘이란?
그래프를 사용하는 최단거리 알고리즘 중 하나이다. 알고리즘은 배워도 배워도 끝이 없다. 하나 배우면 앞에 배운거 까먹고 ㅎㅎ.. 그래서 이렇게 기록을 해놔야 한다. 다익스트라 알고리즘이라는 많이들 사용하는 알고리즘이 있는데 왜 벨만-포드 알고리즘을 써야하는 경우가 생기는가?
-> 간선의 가중치가 음수가 포함된 경우에도 최단거리를 구할 수 있기 때문이다. 특히 가중치가 음수인 경우 간선을 거치면 거칠수록 최단거리가 점점 작아져 음의 무한대로 발산하는 경우가 생기는데, 벨만-포드 알고리즘을 통해 이러한 경우를 구별할 수 있다.
💡 어떤 원리인데?
기본적인 원리는 다익스트라 알고리즘과 같다. 다른점은 다익스트라 알고리즘은 하나의 정점을 기준으로 해당 정점에 연결된 간선들과 정점을 고려했다면 벨만-포드 알고리즘은 모든 정점을 돌면서 모든 간선을 고려해야 한다. 왜냐하면 가중치가 음수인 간선은 항상 최단거리를 줄일 여지가 있기 때문이다. 따라서 벨만-포드 알고리즘의 시간복잡도는 O(|V||E|)로 다익스트라 알고리즘보다는 느리다.
그래프를 사용하는 최단거리 알고리즘 중 하나이다. 알고리즘은 배워도 배워도 끝이 없다. 하나 배우면 앞에 배운거 까먹고 ㅎㅎ.. 그래서 이렇게 기록을 해놔야 한다. 다익스트라 알고리즘이라는 많이들 사용하는 알고리즘이 있는데 왜 벨만-포드 알고리즘을 써야하는 경우가 생기는가?
-> 간선의 가중치가 음수가 포함된 경우에도 최단거리를 구할 수 있기 때문이다. 특히 가중치가 음수인 경우 간선을 거치면 거칠수록 최단거리가 점점 작아져 음의 무한대로 발산하는 경우가 생기는데, 벨만-포드 알고리즘을 통해 이러한 경우를 구별할 수 있다.
기본적인 원리는 다익스트라 알고리즘과 같다. 다른점은 다익스트라 알고리즘은 하나의 정점을 기준으로 해당 정점에 연결된 간선들과 정점을 고려했다면 벨만-포드 알고리즘은 모든 정점을 돌면서 모든 간선을 고려해야 한다. 왜냐하면 가중치가 음수인 간선은 항상 최단거리를 줄일 여지가 있기 때문이다. 따라서 벨만-포드 알고리즘의 시간복잡도는 O(|V||E|)로 다익스트라 알고리즘보다는 느리다.
알고리즘 | 특징 | 시간복잡도 |
---|---|---|
다익스트라 | 특정 노드에 대한 다른 노드까지의 최단거리, 가중치는 양수로만 이루어져야 함 | O(|E|+|V|log |V|) |
벨만-포드 | 특정 노드에 대한 다른 노드까지의 최단거리, 음수가 포함된 가중치까지 커버 가능 | O(|V||E|) |
💡 구현 코드
일반화한 벨만-포드 알고리즘 코드는 아니고 백준의 11657번 타임머신 코드이다. 그냥 벨만-포드를 정석적으로 사용하면 되는 문제라서 바로 올린다.
import sys
input = sys.stdin.readline
INF = 1e9
# 벨만 포드 알고리즘
def bf(start):
# 시작 노드는 최단거리가 자기 자신이므로 0으로 줌
dists[start] = 0
# 값을 계속해서 갱신하기 때문에 N번 순회함
# N-1번 순회해도 되는데 N번 순회하는 이유는 음수 간선이 사이클로 존재할 경우 최단 거리를 표시할 수 없는 경우가 발생하는지 여부를 판단하기 위함
for i in range(N):
# 모든 간선을 순회함
for j in range(M):
# 간선의 정보를 저장한 배열에서 현재 노드, 연결된 노드, 값을 가져옴
cur_node = edges[j][0]
next_node = edges[j][1]
cost = edges[j][2]
# cur_node를 거쳐서 next_node로 도달했을 때의 거리값이 최단거리 배열에 기록된 거리값보다 작으면 값을 갱신해줌
if dists[cur_node]!=INF and dists[next_node] > dists[cur_node] + cost:
dists[next_node] = dists[cur_node] + cost
# 이미 N-1번 순회해서 값의 갱신이 더이상 일어나지 않아야 하는데 갱신이 일어난다는 것은 음수 간선에 의한 순환이 일어난다는 것임
if i==N-1:
return True
return False
# 노드의 개수 N, 간선의 개수 M
N, M = map(int, input().split())
# 간선의 정보를 저장할 배열
edges = []
# 1번 노드로부터의 최단 거리를 저장할 배열
dists = [INF] * (N+1)
# 간선의 정보를 입력받음 각 정보는 A노드에서 B노드로 갈 때 C의 값을 가짐
for _ in range(M):
A, B, C = map(int, input().split())
edges.append((A, B, C))
isCycle = bf(1)
if isCycle == True:
print(-1)
else:
for i in range(2, N+1):
if dists[i] == INF:
print(-1)
else:
print(dists[i])
Author And Source
이 문제에 관하여([알고리즘][파이썬] 벨만-포드 알고리즘), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@seung_min/알고리즘파이썬-벨만-포드-알고리즘
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
일반화한 벨만-포드 알고리즘 코드는 아니고 백준의 11657번 타임머신 코드이다. 그냥 벨만-포드를 정석적으로 사용하면 되는 문제라서 바로 올린다.
import sys
input = sys.stdin.readline
INF = 1e9
# 벨만 포드 알고리즘
def bf(start):
# 시작 노드는 최단거리가 자기 자신이므로 0으로 줌
dists[start] = 0
# 값을 계속해서 갱신하기 때문에 N번 순회함
# N-1번 순회해도 되는데 N번 순회하는 이유는 음수 간선이 사이클로 존재할 경우 최단 거리를 표시할 수 없는 경우가 발생하는지 여부를 판단하기 위함
for i in range(N):
# 모든 간선을 순회함
for j in range(M):
# 간선의 정보를 저장한 배열에서 현재 노드, 연결된 노드, 값을 가져옴
cur_node = edges[j][0]
next_node = edges[j][1]
cost = edges[j][2]
# cur_node를 거쳐서 next_node로 도달했을 때의 거리값이 최단거리 배열에 기록된 거리값보다 작으면 값을 갱신해줌
if dists[cur_node]!=INF and dists[next_node] > dists[cur_node] + cost:
dists[next_node] = dists[cur_node] + cost
# 이미 N-1번 순회해서 값의 갱신이 더이상 일어나지 않아야 하는데 갱신이 일어난다는 것은 음수 간선에 의한 순환이 일어난다는 것임
if i==N-1:
return True
return False
# 노드의 개수 N, 간선의 개수 M
N, M = map(int, input().split())
# 간선의 정보를 저장할 배열
edges = []
# 1번 노드로부터의 최단 거리를 저장할 배열
dists = [INF] * (N+1)
# 간선의 정보를 입력받음 각 정보는 A노드에서 B노드로 갈 때 C의 값을 가짐
for _ in range(M):
A, B, C = map(int, input().split())
edges.append((A, B, C))
isCycle = bf(1)
if isCycle == True:
print(-1)
else:
for i in range(2, N+1):
if dists[i] == INF:
print(-1)
else:
print(dists[i])
Author And Source
이 문제에 관하여([알고리즘][파이썬] 벨만-포드 알고리즘), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@seung_min/알고리즘파이썬-벨만-포드-알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)