벨만포드는 또다른 최단경로 알고리즘으로, 모든 간선의 가중치가 0 이상이어야 하는 다익스트라와는 달리 가중치가 음수일때도 적용할 수 있다. 다만 시간복잡도는 다익스트라보다는 오래 걸리는 O(VE)이다. (다익스트라는 O(ElogV)) 다익스트라는 그리디였다면, 벨만포드는 다이나믹프로그래밍이다.
다익스트라와는 큰 구조가 다른데, 존재하는 모든 간선을 돌아보면서 이 간선을 통할 수도 있는 최단경로들의 거리를 갱신한다.
(루프를 V-1번 돌리는데, K번째 루프에서는 시작점으로부터 각 정점으로 K개의 간선을 거쳐서 도달할 수 있는 최단경로를 다 갱신해주는 것, K-1번째 루프까지는 최대 K-1개 간선을 거치는 최단경로를 다 구해놓았다고 생각하고 K번째에서 그 정보들을 사용하여 다른 최단경로를 구한다)
이때, 음의 가중치가 있는 그래프에서 최단경로를 구할 때 항상 염두에 두어야 하는것이 있다. 바로 음의 사이클(음수 사이클)인데, 벨만 포드 문제에서 반드시 등장하는 요소이다.
음의 사이클의 존재 유무는 루프를 한번 더 돌아서 V번 돌면 된다. 왜냐하면 최단경로는 같은 정점을 두 번 지날 일이 없기 때문에 가능한 최단 경로의 간선 개수는 최대 V-1개 이기 때문이다. 이런 특징 때문에 V번 돌았을 때 V-1번 루프를 돌았을 때와 달리 최단경로가 갱신된다면 그것은 음의 사이클이 존재한다는 것이다.
벨만포드 문제는 다익스트라와 플로이드워셜에 비해 보기가 힘들지만 나왔다 하면 타임머신이나 블랙홀 등 과거로 가는 행동과 연관이 있다.
배운것을 기록하자