https://yabmoons.tistory.com/365
[ 벨만포드 알고리즘 ] 개념과 구현방법 (C++)
이번 글에서는 벨만포드 알고리즘에 대해서 알아보자. 1. 벨만포드 알고리즘 ?? 그래프 알고리즘에서 '최소비용'을 구하는 대표적인 알고리즘으로는 '다익스트라 알고리즘', '벨만포드 알고리즘'
yabmoons.tistory.com
위 블로그를 참고해서 이해했다.
왼쪽에서부터 오른쪽, 위에서 밑으로 벨만포드의 진행 과정을 4단계까지 진행해보았다.
첫번째 노드의 dist를 0으로 초기화하고 모든 간선들을 다 순회한다.
시작 노드의 dist가 무한대가 아니면 그 노드를 거쳐가는게 더 짧은지 계산해본다.
V-1만큼 돌리고 한번 더 벨만포드 알고리즘을 돌려서 최소비용이 변하는 노드가 있으면 음의 사이클이 존재한다고 결론지을 수 있다.
