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

*참고 - 나동빈 유튜브

 

https://gae-gi-da.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Dijkstra

알고리즘 - 다익스트라 알고리즘(Dijkstra)

다익스트라 알고리즘은 이전 포스트에서 말했듯이,

모든 간선의 가중치가 양수일 때만 적용이 가능하다.

현실의 상황에서는 간선의 가중치, 즉 거리가 음의 시간이 소요되는 것이 불가능하기에

다익스트라 알고리즘이 언제나 적용이 가능하고 실제로 많은 내비게이션 등의 시스템에서

근간이 되는 알고리즘이기도 하다.

 

다만 수학적으로는 음의 간선도 충분히 존재할 수 있다.

특히 아래처럼 간선들의 총합이 음수가 되는 사이클이 존재할 경우, 해당 노드와 연결된 모든 노드에 대한 거리가

음의 무한대가 돼버린다.

음수 간선 사이클

벨만-포드 알고리즘의 특징은 음수 간선이 포함된 경우에도 사용할 수 있으며

음수 간선의 순환(사이클)을 감지할 수 있다는 것이다.

다만 다익스트랑 알고리즘의 수행시간인 O(ElogV)에 비해

O(VE)로 좀 더 느리다.

 

벨만 포드 알고리즘의 과정은 다음과 같다.

 

1. 출발 노드를 설정한다.

2. 최단 거리 테이블을 초기화한다.

3. 다음의 과정을 N-1번 반복한다.

1) 전체 간선 E를 하나씩 확인한다.

2) 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

 

(만약 3번 과정을 한 번더, 즉 n번째 반복했을 시에 데이터 갱신이 발생한다면,

이는 음수 간선 순환이 존재한다는 말과 같다.)

 

코드는 다음과 같으면 보다시피 노드의 개수 n과 간선의 개수 m의 곱만큼

반복문이 진행된다는 것을 확인할 수 있다.

import sys
input = sys.stdin.readline
INF = int(1e9)

n,m = map(int, input().split())
edges = []
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
    
    for i in range(n):
    	for j in range(m):
            cur = edges[j][0]
            next_node = edges[j][1]
            cost = edges[j][2]
            
            if dist[cur] != INF and dist[next_node] > dist[cur] + cost:
            	dist[next_node] = dist[cur] + cost
                if i == n-1:
                	return True
    return False
    
is_negative_cycle = bf(1)

if is_negative_cycle:
	print('-1')
else:
	for i in range(2,n+1):
    	if dist[i] == INF:
        	print('-1')
        else:
        	print(dist[i])