[D-12] 🤔벨만-포드 & 플로이드-워셜

📍벨만-포드

✅ 정의

벨만-포드(bellman-ford-moore) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
음수 사이클을 판별하는 문제가 더 빈번하게 출제된다.

 

✅ 특징

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

 

✅ 핵심 이론

1. 에지 리스트로 그래프를 구현하고 최단 경로 배열 초기화하기
2. 모든 에지를 확인해 정답 배열 업데이트하기
3. 음수 사이클 유무 확인하기

 

1. 에지 리스트로 그래프를 구현하고 최단 경로 배열 초기화하기
- 벨만-포드 알고리즘은 에지를 중심으로 동작하므로 그래프를 에지 리스트로 구현한다.
- 최단 경로 배열은 출발 노드는 0, 나머지 노드는 무한대로 초기화한다.
- edge 클래스는 노드 변수 2개와 가중치 변수로 구성돼 있다.

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

 

✅ 업데이트 조건과 방법

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

음수 사이클이 없을 때 최대 에지 개수가 나오려면 사향 트리 형태에서 양 도착 노드를 선택해야 한다.
에지의 출발 노드를 s, 종료 노드를 e, 에지의 가중치를 w로 가정한다.

 

3. 음수 사이클 유무 확인하기
- 모든 에지를 한 번씩 다시 사용해 업데이트되는 노드가 발생하는지 확인한다.
- 음수 사이클이 존재하면 이 사이클을 무한하게 돌 수록 가중치가 계속 감소하므로 최단 거리를 구할 수 없다. (2단계에서 도출한 정답 배열이 무의미하기 때문이다.)

 

✅ 수행 과정

1. 모든 에지와 관련된 정보를 가져온 후 다음 조건에 따라 거리 배열의 값을 업데이트한다.
  - 출발 노드가 방문한 적이 없는 노드(출발 노드 거리 == INF)일 때 값을 업데이트하지 않는다.
  - 출발 노드의 거리 배열값 + 에지 가중치 < 종료 노드의 거리 배열값일 대 종료 노드의 거리 배열값을 업데이트한다.
2. '노드 개수 - 1'번만큼 1을 반복한다.
3. 음수 사이클 유무를 알기 위해 모든 에지에 관해 다시 한 번 1을 수행한다. 이 때 한 번이라도 값이 업데이트되면 음수 사이클이 존재한다고 판단한다.

 

---

📍 플로이드-워셜

✅ 정의

- 플로이드-워셜(floyd-warshall) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
- 완성된 배열은 모든 노드 간의 최단 거리를 알려준다.
- 플로이드-워셜 알고리즘을 사용해야 하는 문제가 나오면,
   일반적으로 노드의 개수의 범위가 다른 그래프에 비해 적게 나타나는 것을 알 수 있다.

 

이미지 출처 : 플로이드 워셜, https://velog.io/@kimdukbae/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Floyd-Warshall-Algorithm

✅ 특징

- 모든 노드 간에 최단 경로를 탐색한다.
- 음수 가중치 에지가 있어도 수행할 수 있다.
- 동적 계획법의 원리를 이용해 알고리즘에 접근한다.
- 시간 복잡도는 O(V^3)이다.

 

✅ 핵심 이론

전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이루어진다.

✔️ 플로이드-워셜 점화식
D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

✅ 구현 과정

1. 배열을 선언하고 초기화하기
2. 최단 거리 배열에 그래프 데이터 저장하기
3. 점화식으로 배열 업데이트하기

 

1. 배열을 선언하고 초기화하기
- D[S][E]는 노드 S에서 노드 E까지의 최단 거리를 저장하는 배열이라 정의한다.
- S와 E의 값이 같은 칸은 0, 다른 칸은 ∞로 초기화한다.
- 여기에서 S==E는 자기 자신에게 가는 데 걸리는 최단 경로값을 의미한다.

---

2. 최단 거리 배열에 그래프 데이터 저장하기
- 출발 노드는 S, 도착 노드는 E, 이 에지의 가중치는 W라고 했을 때, D[S][E] = W로 에지의 정보를 배열에 입력한다.
- 플로이드-워셜 알고리즘은 그래프를 인접 행렬로 표현한다.

---

3. 점화식으로 배열 업데이트하기
- 기존에 구했던 점화식을 3중 for문의 형태로 반복하면서 배열의 값을 업데이트한다.

// 플로이드-워셜 알고리즘 로직
for 경유 K에 관해 (1 ~ N)    // N: 노드 개수
	for 출발 노드 S에 관해 (1 ~ N)
    	for 도착 노드 E에 관해 (1 ~ N)
        	D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])