재원블로그 재원블로그

최단 경로를 구하는 두번째 알고리즘 벨만 포드 알고리즘이다. 이 알고리즘은 다익스트라와 마찬가지로 하나의 시작점에서 다른 정점들간의 최소 시간을 구하는 알고리즘이다. 최악 시간 복잡도는 O(|V||E|)이다. 여기서 |V|는 정점의 개수, |E|는 간선의 개수이다. 다익스트라는 최악 시간 복잡도가 O(|E| + |V| log|V|) 인데 이 알고리즘을 사용하는 이유는 음수 가중치에 대해서도 적용할 수 있기 때문이다. 또한 음수 사이클의 존재 유무까지 판단할 수 있다. 이 알고리즘은 다익스트라와 같이 BFS 기반의 연산을 하는 것이 아닌 플로이드 워셜 알고리즘같이 다중 반복을 통해 문제를 해결한다. 그래서 우선순위 큐를 사용하지 않는다. 이 알고리즘은 초기에 start의 dist가 0이라는 것 빼고 모든 ..