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

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

single source 문제

음수 가중치가 있고, 음수 사이클이 없는 그래프에서 한정점에서 다른 모든 정점까지의 최단경로 및 거리를 구하는 알고리즘

음수사이클이 있으면 무한히 사이클을 루프할수 있어서 최단경로를 구할수 없다.

단 벨만포드알고리즘의 장점은 그래프내에 음수사이클이 있음을 판단할수 있다.

1. 시작점을 제외한 모든 정점들을 최단거리를 무한대로 설정

2. 그래프 모든 간선에 대해

3. 정점 A에서 B로의 방향을 가지고 있는 각 간선에 대해

현재 정점 B까지의 거리가 정점 A까지의 거리 + 현재 간선의 거리의 합보다 클경우

정점 B의 경로와 거리를 갱신해준다.

4. 이들 경로와 거리의 갱신이 일어나지 않을때까지 반복한다.

만약 정점의 수 만큼의 시행 이후에도 경로와 거리의 갱신이 일어날 경우

음수사이클이 존재한다.