알고리즘 공부방

벨만-포드 알고리즘은 다익스트라 알고리즘과는 다른 방법으로 그래프에서의 단일 시작점에서의 최단 거리를 구하는 알고리즘이다. 다익스트라 알고리즘은 $O(ElogV)$의 매우 빠른 시간복잡도를 갖고 있지만, 음수간선에 대해 최단거리를 구하지 못한다는 단점이 있다. 벨만-포드 알고리즘은 이를 보완하여 음수 간선에 대해서도 최단거리를 구할 수 있게 해 준다. 기본적으로, 그래프에서 각 간선을 "완화"하는 작업을 반복한 후, 이러한 과정을 적질히 계속하여 결국은 모든 노드에 대해 최단 거리를 구해 낸다. 일단, 모든 간선에 대해 이와 같은 성질이 성립한다. u에서 v로의 간선 w가 존재한다면, $dist[v]dist[u]+w$ 라면 $dist[v]=dist[u]+w$ 로 조금 더 작게 만들어 줄 수 있다. 이를 ..