벨만 포드

벨만 포드(Bellman Ford)는 간선에 비용이 있는 그래프에서

시작점부터 다른 정점까지의 최단거리를 구할 수 있는 단일 시작점 최단거리 알고리즘입니다.

이는 다익스트라 알고리즘과 동일하지만 간선의 비용이 음수일 때도 사용할 수 있습니다.

벨만 포드 알고리즘은 다익스트라와 동일하게 dist배열을 사용하며 dist[i]는 시작점에서 i번 정점까지의 최단거리를 뜻합니다.

시작점의 dist값은 0, 나머지 모든 정점은 무한대로 초기화 한 뒤 dist배열을 갱신하는 작업을 진행하는데

최단 거리는 정점 개수가 V일 때 최대 V-1개의 간선을 거쳐야 한다는 원리를 이용하여

V-1번의 루프를 돌며 k번째 루프에서는 시작점으로부터 k개의 간선을 거쳐 도달할 수 있는 최단 경로를 dist에 저장합니다.

이 때 최단 거리가 V개 이상의 간선을 거쳐야 하는 경우가 존재하는 데 이는 음수 사이클이 존재할 때입니다.

음수 사이클이 존재할 경우 루프를 돌면 돌수록 dist값이 계속 작아진다는 것을 이용하여

V-1번 루프이후 한번의 루프를 더 돌아 이 때도 dist값이 갱신되었다면 음수 사이클이 있는 것으로 확인 할 수 있습니다.

시간복잡도는 정점 개수가 V 간선 개수가 E일 때 V번의 루프 내에서 모든 간선을 순회하므로 O(VE)이며

추후 유량파트의 MCMF에서 이 알고리즘을 변형하여 사용하므로 알아두면 좋습니다.

기본 문제

11657번: 타임머신