코딩못하는사람

벨만-포드 알고리즘 다익스트라와 마찬가지로 SSP알고리즘인 벨만-포드 알고리즘은 음의 가중치를 다룰 수 있다. 그런데 다음과 같이 음의 가중치로 인해 순환 구조를 가진다면 최단경로를 구할 수 없다. 따라서 벨만-포드 알고리즘은 최단경로를 구하는 것과 이 그래프에서 최단경로를 구할 수 있는지 없는지를 판별하는 과정 두 과정으로 나눠진다. 벨만 포드 알고리즘은 V-1번 모든 간선을 Relax하는 작업을 수행한다. 최단경로구하기 동작과정은 각 정점들을 돌아 가면서 모든 간선들을 탐색한다, 단 맨 처음은 시작점부터 탐색한다( 처음 이후에는 순서 상관없음) D(s,v)=D(s,u)+w(u,v) 이 과정을 V-1번 탐색하는 이유는 s에서 v까지 가는 경우에서 v를 뺀 모든 경로가 각각 최단거리일 수 있기 때문이다(..