타임머신

벨만-포드 알고리즘이란? 벨만-포드 알고리즘은, 한 노드에서 다른 노드까지의 거리를 구하는 알고리즘이다. 다익스트라 알고리즘이 모든 비용(가중치)가 양수인 경우에만 사용할 수 있는 반면에 벨만-포드 알고리즘은 노드 간의 간선 비용(가중치)가 음수인 경우에도 사용할 수 있다. 다만, 시간 복잡도는 벨만-포드가 더 크기 때문에 비용(가중치)가 모두 양수라면 굳이 벨만-포드를 사용할 필요는 없다. 음수 사이클이 문제가 되는 이유 단순 음수 간선일 경우 : 단순 경로이므로 그대로 비용을 계산. 사이클이 존재하나 양수값이 더 클 경우 : 사이클을 순환하여도 이득이 없으므로 그대로 진행. 사이클이 존재하고 음수값이 더 클 경우 : 사이클을 순환할 수록 비용이 감소해 최소 비용을 찾는 입장에서 사이클을 무한히 순환하..