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

0. 개요

벨만포드 알고리즘은,

그래프 중 음수간선이 있을 때 시작 정점에서부터 임의 정점까지 거리를 알 수 있다.

음의 사이클의 존재여부도 위 알고리즘을 통해 감지 할 수 있다.

최단거리 알고리즘 중에서 음수 간선이 있어도 유효하다.

1. 구현

벨만포드 알고리즘은 [ 1번 정점부터 N번 정점까지 최단거리를 BFS로 최신화하는 루프 ]를 N-1번 순회하는 알고리즘이다.

2. 설명

 위의 그래프를 예시를 들어보자. 1번 노드를 출발점이라 가정하자.

정점이 4개이므로 1번~4번정점까지 총 3(4-1)번 반복하면 된다.

정점 번호	1	2	3	4
dist	0	INF	INF	INF

1번째 반복

정점 번호	1	2	3	4
dist	0	INF	-8	-12

1번 정점부터 4번 정점까지 순차적으로 BFS로 최단거리를 갱신하면 다음과 같을 것이다.

3번 정점에서 @번 정점으로 가는 간선이 존재하지만,

3번 정점에서 BFS로 작동할 때 출발 정점으로부터 3번 정점까지의 거리가 INF이므로 3->2 간선을 이용해서 최신화 할 수 없다.

2번째 반복 

정점 번호	1	2	3	4
dist	0	-5	-8	-12

1번째 반복에서 사용할 수 없었던 3번 정점 -> 2번 정점 간선을 사용해서 3번 정점을 최신화 시킬 수 있었다. 

3번째 반복

정점 번호	1	2	3	4
dist	-1	-5	-8	-12

최단거리인지 체크

N-1회 반복 했을 때 dist[2] 를 보면 1번 정점에서 2번 정점까지의 최단거리가 -5임을 알 수 있다.

하지만 여기서 1번 더 반복하게 된다면

정점 번호	1	2	3	4
dist	-1	-5	-8	-13

위 표 처럼 dist[4] 값이 변하기에 무한 루프적으로 모든 정점의 최단거리가 [ - 무한대 ] 가 될 것이다.

그러므로 N-1회 반복한 후 다시 한번 1번 정점에서 N번 정점까지 BFS로 순회해서 어느 한 정점이라도 최단거리가 갱신이 된다면 음의 사이클이 존재하는 것이다.

갱신이 되지 않았다면, dist배열은 출발 정점으로 부터 각 정점까지의 최단 거리를 보장할 수 있다.

3. 문제 및 코드

https://www.acmicpc.net/problem/11657

import sys

INF = sys.maxsize
input = sys.stdin.readline


def main():
	city_num, edge_num = map(int, input().split(' '))
	
	traffic = [INF for _ in range(city_num + 1)]
	edges = [[] for _ in range(city_num + 1)]
	
	for _ in range(edge_num):
		S, V, W = map(int, input().split(' '))
		edges[S].append((W, V))
	traffic[1] = 0
	
	for _ in range(city_num - 1):
		Bellman_Ford(edges, traffic, city_num)
	
	if check_Loop(edges, traffic, city_num):
		for i in range(2, city_num + 1):
			print(traffic[i] if traffic[i] < INF else -1)
	else:
		print(-1)


def Bellman_Ford(edges, traffic, city_num):
	for i in range(1, city_num + 1):
		if traffic[i] == INF:
			continue
		for W, V in edges[i]:
			if traffic[i] + W < traffic[V]:
				traffic[V] = traffic[i] + W


def check_Loop(edges, traffic, city_num):
	for i in range(1, city_num + 1):
		if traffic[i] == INF:
			continue
		for W, V in edges[i]:
			if traffic[V] != INF and traffic[i] + W < traffic[V]:
				return False
	return True


main()

4. 시간 복잡도

간선의 개수를 E, 정점의 개수를 V라고 했을 때,

1번 정점부터 마지막 정점까지 순회한 것은 모든 간선을 탐색하기 위함이므로 E번 코드가 수행되고

모든 간선 탐색을 V-1번 반복하기에

시간 복잡도는 O(|V||E|) 이다.