[알골90제] 81번 - 벨만포드 알고리즘(다시풀기)

최소 비용으로 출발정점에서 도착정점까지 가는 경로를 찾는 것

 

- 간선을 1번만에 갈 수 있다

- 간선을 2번만에 갈 수 있다

- 간선을 3번만에 갈 수 있다

.

.

.

정점이 5개면 간선을 5개를 썻다면,,? 2번 정점을 2개 들린 회로가 발생한다는 것

싸이클이 있다는 것은 가중치가 음수인 값이 있다는것

=> 음의 싸이클이 존재하지 않는 한 벨만포드 사용가능

=> 노드가 5개라면 간선 5개를 택할 수 없음

 

정점이 n개면

간선을 n-1개 사용하는 것이 가장 긴 경로다