다익스트라
벨만-포드 ✔️
플로이드-워셜

벨만-포드

벨만-포드 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.

기능	특징	시간 복잡도(노드 수:V, 에지 수: E)
특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색	- 음수 가중치 에지가 있어도 수행할 수 있음 - 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음	O(VE)

✅ 벨만-포드의 핵심이론

➡️ 1단계: 에지 리스트로 그래프를 구현하고 최단 경로 배열 초기화하기

벨만-포드 알고리즘은 에지를 중심으로 동작하므로 그래프를 에지 리스트로 구현한다.
또한 최단 경로 배열은 출발 노드는 0, 나머지 노드는 무한대로 초기화 한다.
다음 예에서 출발 노드를 1로 선택해 벨만-포드 알고리즘을 진행하며 알아보자

➡️ 2단계: 모든 에지를 확인해 정답 배열 업데이트하기

최단 거리 배열에서 업데이트 반복 횟수는 노드 개수 -1이다.
노드 개수가 N이고, 음수 사이클이 없을 때 특정 두 노드의 최단거리를 구성할 수 있는 에지의 최대 개수는 N-1이기 때문이다.
특정 에지 E = (s, e, w)에서 다음 조건을 만족하면 업데이트를 실행한다.

업데이트 조건과 방법

D[s] ≠ ∞이며 D[e] > D[s] + w일 때 D[e] = D[s] + w로 배열의 값을 업데이트 한다.