벨만-포드

 

---

📍 정의 및 특징

가중치가 있는 그래프에서 특정 출발 노드 → 다른 모든 노드까지의 최단 경로 탐색

 

- 음수 가중치 에지가 있어도 수행 가능

- 음수 사이클 존재 여부 판단

- 시간 복잡도 : O(VE)

 

#가중치O  #음수사이클 

 

+ DP 활용

 

 

📍 필요 변수

1. 에지 클래스

    - 노드 변수 2개 (start, end)

    - 가중치 변수

2. 그래프 에지 리스트

   - ArrayList<Edge>

3. 최단 경로 배열

   - int[]

   - 출발 노드 : 0 / 나머지 노드 :  ∞ 

4. 사이클 판단 변수

   - boolean

 

 

📍 실행 과정

1. 그래프 에지 리스트 & 최단 경로 배열 초기화   (출발 노드 : 0 / 나머지 : ∞)
2. 모든 에지 E = (s,e,w) 확인해 정답 배열 업데이트 → (노드 개수 - 1)번 반복
   ⇒ D[s] ≠ ∞ & D[e] > D[s] + w 이면, D[e] = D[s] + w로 업데이트
3. 모든 에지 한 번 더 반복해 음수 사이클 유무 확인
   (업데이트 되는 노드가 있으면, 음수 사이클 존재하는 것)

 

 

➕ 예제

[백준/JAVA] 11657번: 타임머신

 

---

(참고)

Do it 알고리즘 코딩 테스트 자바편