벨만-포드 개념 벨만 포드 알고리즘은 가중치가 존재하는 그래프에서 최단 경로를 구하고자 할 때 사용할 수 있는 알고리즘이다. 보통 위와 같은 유형의 문제를 풀기 위해 다익스트라 알고리즘을 먼저 학습한다. 결론부터 말하자면 다익스트라 알고리즘의 경우 음수 간선이 존재하는 경우 문제를 해결하지 못 할 수 있다. 다익스트라 음수 간선 위에서 다익스트라의 경우 음수 간선이 존재하면 문제를 해결하지 못한다고 하지 않았고 못 할 수 도 있다고 했다. 아래의 그래프를 통해 자세히 이해해보자. 단순한 음의 간선 : s -> a -> b -> g 경로에 -4(a -> b) 음의 간선이 있어도 문제가 발생하지 않음 순환하지 않는 싸이클 : s -> c > -> d 경로 이후 d->c로 가는 경우 -3 음의 간선이 있지만 ..