벨만-포드 알고리즘 (Bellman-Ford Algorithm)

☞ 그래프의 최단 경로를 알고 싶고, 그래프에 음수 간선이 있으며, 음수 사이클이 존재 할 때 다익스트라 알고리즘을 사용해 최단 경로를 구해도 될까? -> 정당성에 성립되지 않습니다. 따라서 음수 간선이 존재하고 음수 사이클이 존재한다는 것을 확인하고 싶을 때 Bellman-Ford Algorithm을 사용해야합니다. ☞ 벨만-포드 알고리즘이란 무엇일까? 벨만포드 알고리즘 원리는 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여가는 방식입니다. 여기서 상한은 upper 배열에 저장하며 이 upper의 값은 알고리즘이 진행됨에 따라 점점 줄어들고 알고리즘이 종료되면 실제 최단 거리를 담게 되는 원리입니다. ☞ 벨만-포드 알고리즘 동작..