알고리즘/알고리즘 기초공부
[알고리즘] 벨만-포드 알고리즘
이숭간
2021. 8. 11. 23:22
728x90
벨만포드 알고리즘
최단경로라는것은 같은정점을 두번 지날일이 없기때문에 최단 경로의 간선개수는 최대 V-1개이다. 따라서 루프를 V-1번 (V는 노드의수) 돌리는데(최악의 경우까지 모두 커버가 가능), k번째 루프에서는 시작점으로부터 각 정점으로 k개의 간선을 거쳐서 도달할 수 있는 최단경로를 다 갱신해주자는 게 기본 아이디어 ( 이렇기 때문에 음의순환을 찾을때 한번더 수행하는것 )
- 음수간선이 포함된 상황에서 최단거리 찾기
- 모든간선이 양수일때는 다익스트라를 사용하면 된다.
- 음수 간선의 순환이 발생하는 경우, 최단거리가 음의 무한인 노드가 발생한다. (계속해서 줄일수있으니까 무한대로 순환)
간선에 관하여 최단 경로문제는 다음과 같이 분류된다.
- 모든 간선이 양수인 경우 ( 다익스트라, 플로이드 와샬)
- 음수 간선이 있는 경우 ( 벨만-포드 )
- 음수 간선 순환이 있는 경우
- 음수 간선 순환이 있는 경우
벨만포드 최단경로 알고리즘은 음의 간선이 포함된 상황에서도 사용가능하다.
또한 음수 간선의 순환을 감지할 수 있다.
기본 시간복잡도 : O(VE)
동작과정
- 출발노드 설정
- 최단거리 테이블 초기화
- 다음의 과정을 n-1번 반복한다.
- 전체 간선 E개를 하나씩 확인한다.
- 각 건선을 거쳐 다른노드로 가는 비용을 계산하여 최단거리 테이블을 갱신한다.
- 만약 음수 간선의 순환이 발생하는지 알고 싶다면 3번과정을 한번 더 수행한다. 이때 만약 최단거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것이다.
벨만포드 VS 다익스트라
- 다익스트라
- 매번 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다.
- 음수간선이 없다면 최적의 해 찾기가능
- 벨만포드
- 매번 모든간선을 확인 (= 다익스트라 알고리즘에서의 최적의 해를 항상 포함한다)
- 다익스트라에 비해서는 시간이 오래걸리지만 음수 간선의 순환을 탐지할 수 있다.
알고리즘 코드
이때, 음의 간선이 존재하기 때문에 간선 (u, v)를 볼 때 먼저 dist[u]가 아직 INF인지 확인을 해야 한다.
구현에 따라서 둘 다 시작점에서 도달 불가능한 정점 u, v가 존재하고 (u, v) 가중치가 음수일 때
dist[u] = INF, dist[v] = INF-cost 꼴이 나올 수도 있기 때문!!!
# 노드개수, 간선개수
n,m = map(int, input().split())
# 간선정보를 담을 리스트
edges = []
# 최단거리 테이블 초기화
INF = int(1e9)
dist = [INF] * (n+1)
# 간선정보 입력받기
for _ in range(m):
a,b,c = map(int, input().split())
edges.append((a,b,c))
def bf(start):
# 시작노드에 대해 초기화
dist[start] = 0
# 전체 n번의 라운드를 반복 (전체노드를 방문)
for i in range(n):
# 방문할때마다 모든간선을 확인
for j in range(m):
curr = edges[j][0] # 현재노드
next_node = edges[j][1] # 목적지노드
cost = edges[j][2]
# 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더짧은 경우
if dist[curr] != INF and dist[next_node] > dist[curr] + cost:
dist[next_node] = dist[curr] + cost
if i==n-1: #n번째 라운드에서 값이 갱신되었다면 음수순환이 존재한다는것
return True
return False
negative_cycle = bf(1)
if negative_cycle:
print("음수순환이 존재한다.")
else:
# 1번노드를 제외한 다른 모든 노드로 가는 최단거리
for i in range(2, n+1):
if dist[i] == INF:
print('-1') #출발노드에서 그 지점까지 가는방법 없음
else:
print(dist[i])
참고 :
https://ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/