벨만포드 알고리즘 설명 및 백준 11657번 문제 풀이 https://chb2005.tistory.com/79 [JAVA] 벨만포드 알고리즘 (Bellman-Ford) Bellman-Ford 알고리즘 이란? 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘 + 음수 사이클 존재 여부를 알 수 있음 다익스트라와는 달리 가중치에 음수가 있어도 사용 가능 시간복 chb2005.tistory.com

Bellman-Ford 알고리즘 이란? 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘 + 음수 사이클 존재 여부를 알 수 있음 다익스트라와는 달리 가중치에 음수가 있어도 사용 가능 시간복잡도 : O(NE) (N:노드의 수, E: 엣지의 수) 다음과 같은 그래프가 있다고 가정 다익스트라로 노드 1에서 모든 노드로의 거리를 구하면 1 -> 2 = 1 1 -> 2 -> 3 = 2 1 -> 2 -> 3 -> 4 = 4 가 되고 노드 2는 이미 방문했기 때문에 4 -> 2 경로는 고려하지 않음 결과적으로 1 -> 2의 최단경로는 1이 됨 하지만 실제 1 -> 2의 최단경로는 -∞ 임 이를 해결하기 위해 벨만포드 알고리즘 탄생 Bellman-Ford 원리 엣지는 1->2, 4->2, 2->3, 3->..