벨만-포드 알고리즘 (Bellman-Ford Algorithm)시작 노드에서부터 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘.다익스트라와 다르기 가중치가 음수인 경우에도 사용이 가능하지만, 최적해를 보장하지는 않는다.=> 벨만-포드 알고리즘을 이용해 가중치가 음수인 사이클을 찾을 수 있다. 시간복잡도의 경우 O(nm)여기서 n은 노드의 개수, m은 간선의 개수. 과정시작 노드에서 다른 모든 노드까지의 길이를 모두 추적.거리의 초기값은 시작노드를 0, 나머지는 INF로 설정하고, 이 값을 계속 줄여나가는 과정을 통해 더 줄일 수 있는 값이 없을 때까지 반복.위와 같은 그래프가 있다고 가정하자. 가장 먼저 파란색 간선을 통해 INF인 값을 줄인다. 3에서 4로 가는 간선을 먼저 보자.3+1 2에서 ..
