벨만 포드 알고리즘이란? 다익스트라 알고리즘처럼 최단경로를 구해주는 알고리즘이다. 시간복잡도는 다익스트라 알고리즘보다 오래 걸리는 $O(|V||E|)$이지만 간선의 가중치가 음수일 때 사용 가능하다. 다익스트라 알고리즘으로는 간선의 가중치가 음수일 때 계속해서 갱신이 일어나므로 무한 반복이 일어나 최단경로를 제대로 구하지 못할 수 있으므로 벨만 포드 알고리즘을 사용한다. 벨만 포드 알고리즘의 핵심은 음수 가중치의 판단이고, 이는 최단 경로가 갱신되는 횟수로 구한다. 다익스트라 알고리즘에서 특정 정점에 대한 최단경로 갱신은 최대 몇 번 일어날 수 있을까? 먼저 가능한 최단 경로의 길이(거치는 정점의 수)를 생각해보자. 모든 정점을 최대 1번만 지날 수 있으므로 그 길이는 |V|이다. 또한 최단 경로 갱신 ..
