음수 간선이 포함되어있는 상황에서 최단거리 혹은 최소비용을 도출하고자 할때 사용할 수 있다(*다익스트라, 플로이드 와샬은 모두 간선이 양수).
다익스트라를 통해 음수간선이 포함되어있는 상황에서 최단거리를 도출해낼 수는 있다. 단, 최단경로가 음의간선을 고려하였어도 양의 정수가 나올 경우에 해당한다.
위처럼 음의간선을 고려하였을때 최단 경로가 음수가 나올 경우 모순에 해당되어, 끝없이 음의 방향으로 최소값을 도출하는 무한반복에 빠지게 된다.
따라서 위의 경우에는 다익스트라를 통해 최소값을 구할 수 없다.
※ 벨만포드 알고리즘은 음수순환이 발생하는지 감지할 수 있고, 기본적으로 다익스트라 알고리즘에 비해 느리다(O(VE)).
※ 다익스트라 알고리즘
※ 벨만포드 알고리즘
N개의 도시가 있다.
1번도시에서 출발하여 나머지 도시로 가는, 가장 빠른 시간을 구하는 알고리즘은?
#음수간선이 포함되어있는 상황에서의 최단거리
#벨만포드 알고리즘
##일단 음수간선인 경우가 있기 때문에 벨만포드 알고리즘.
##참고) 특정 도시에서 모든 도시로의 최단 경로이므로, 간선이 양수라면 다익스트라 사용
## 1<= N <= 500, 1<= M <=6000
import sys
INF = int(1e9)
#노드개수, 간선개수
n, m = map(int ,sys.stdin.readline().split())
#모든 간선에 대한 정보를 담는 리스트
edges = []
#최단 거리 테이블을 일단은 모두 무한으로 초기화
dist = [INF] * (n+1)
#모든 간선 정보를 입력받기
for _ in range(m):
a, b, c = map(int, sys.stdin.readline().split())
#a에서 b로가는 비용이 c
edges.append((a,b,c))
#벨만 포드 알고리즘
def bf(start):
#최초 거쳐가는 노드는 자기자신, 거리는 0
dist[start] = 0
#모든 노드와 간선에 대해 반복
for i in range(n):
for j in range(m):
#어차피 모든 간선을 확인해야하므로
current_node = edges[j][0]
next_node = edges[j][1]
cost = [j][2]
#현재 간선을 거쳐 다른 노드로 이동하는 거리가 더 짧은 경우
if dist[current_node] != INF and dist[next_node] > dist[current_node] + cost:
dist[next_node] = dist[current_node] + cost
# n번째 순환에서도 값이 갱신된다면 음수 순환이 존재하는 것으로 간주
if i == n-1:
return True #음수순환이 존재
return False
#알고리즘 수행
negative_cycle = bf(1) #출발노드는 1
if negative_cycle:
print(-1)
else:
for i in range(2, n+1): #1번노드를 제외하고, 다른 모든 노드로 가기위한 최단거리 출력
if dist[i] == INF:
print(-1)
else:
print(dist[i], end=' ')
이코테 2021 - 벨만포드
https://www.youtube.com/watch?v=Ppimbaxm8d8&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=13