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

오늘 공부할 알고리즘은 벨만 포드 알고리즘(Bellman-Ford Algorithm)이다. 이 알고리즘도 하나의 정점으로부터 다른 정점으로의 최단 거리를 구하는 알고리즘인데, 다익스트라 알고리즘과 다르게 cost가 음수일 때도 사용을 할 수 있다. 

벨만 포드의 점화식을 통해서 어떻게 cost가 음수일 때도 고려해서 최단 거리를 구할 수 있는지 보도록 하겠다. 우선 base가 되는 식은 d(1)(v, u)=length(v, u) 이다. 첫 괄호의 1은 1개의 이하의 간선을 의미하고, d(1)(v,u)는 한개 이하의 간선을 거쳐 v에서 u로 가는 최단 경로의 cost를 뜻한다. length(v, u)는 v에서 u로 가는 edge의 cost를 담고 있으며, 이 경우 v에서 u로의 edge 값이 최단 경로의 cost가 되기 때문에 위의 식과 같다. 계속해서 점화식을 세워보면 d(k+1)(v, u) = min( d(k)(v, u), d(k)(v, i) + length(i, u) ) 이다. 이 점화식을 보면 k+1개 이하의 간선을 거쳐 v에서 u로 가는 최단 경로의 cost는 두 가지의 경우 중 작은 값이라는 것을 알 수 있다. 첫 번째 경우는 k개 이하의 간선을 거쳐 v에서 u로 가는 최단 경로의 cost이고, 두 번째 경우는 k개 이하의 간선을 거쳐 v에서 i로 간 다음 i에서 u로 가는 경우이다. 두번째 경우 k개 이하의 간선을 거치고 또 한 번 더 경로를 거치지만 첫번째 경우보다 작다는 뜻이므로 이때 음수의 cost를 가진 정점을 지남으로써 작은 값을 가지게 되는 경우이다. 이렇게 거치는 edge의 수가 n-1이 될 때까지 모든 경우를 탐색하며 최단 거리를 찾아낼 수 있다. 따라서 이를 통해 찾고자 하는 값은 d(n-1)(v, u) 일 것이다. 

벨만 포드 알고리즘을 통해 cost가 음수일 때도 사용할 수 있다는 장점이 있는 대신 고려해야 할 점도 있다. 바로 v에서 u로 가는 최단 경로를 찾을 때, 그 경로 속에 음수의 사이클이 있으면 d(n-1)(v, u) 를 통해서 최단 경로의 cost를 구할 수 없다. 왜냐하면, 음수의 사이클이 존재한다면 계속해서 그 사이클을 돌 때마다 cost가 줄어들기 때문에 무한루프에 빠질 것이다. 이럴 경우 필요했던 것이 Topological sort였던 것 같은데 다음 포스팅에서 자세히 알아보도록 하겠다!