백엔드 개발자

그래프 최단 거리 알고리즘벨만 포드 알고리즘은 그래프 최단 거리를 구하는 알고리즘 중 하나이다.대표적으로 다익스트라 알고리즘은 모든 간선의 가중치가 양수일 때만 가능하다.다익스트라다익스트라가 어떻게 동작하는지 간단하게 살펴보자.이런 그래프가 있다고 가정한다. A에서 E까지의 최단거리를 구할 것이다.A에서 가능한 경로 중 가장 빠른 경로를 선택하여 이동할 것이다. A에서 B로 가는 경로가 선택되어 A에서 B까지의 경로는 최단 거리가 3인 것을 알 수 있다.이후 B에서 갈 수 있는 경로를 큐에 넣고 다시 탐색을 반복할 것이다. 이렇게 각 최단거리를 구하다 보면 E까지의 최단거리가 11이라는 것을 알 수 있다.그런데 이 방법은 모든 가중치가 양수일 때만 가능하다. 그림처럼 D에서 B로 가는 경로는 -100이기..