17강. 벨만-포드 알고리즘

[ 목차 ]

1. 최단 경로 문제

2. 최단 경로 문제의 구분

3. 음수 간선 값

4. 직전 정점 하위 그래프

5. 완화

6. 벨만-포드 알고리즘

 

1. 최단 경로 문제

1) 최단 경로 : 정점 u에서 다른 정점 v까지의 경로의 값이 가장 작은 경로

2) 정점 u를 시작점, v를 도착점이라 지칭

3) 최단 경로 값

 

2. 최단 경로 문제의 구분

1) 시작점과 도착점의 숙에 따라 구분

2) 싱글 소스 & 싱글 데스티네이션

3) 싱글 소스

4) 싱글 데스티네이션

5) all pairs

 

3. 음수 간선 값

1) s에서 g로 가는 최단 경로 : s - a - b - g

2) s - e - f - e - f ..... - g 의 경로는 음수의 간선 값을 가짐

3) 음수 간선이 문제가 되는 것은 아니지만 음수 순환(모든x)은 문제

4) 시작점 - 도착점까지의 경로 중간에 존재하는 음수 순환이 문제

4. 직전 정점 하위 그래프

1) 최단 경로 트리

2) 최적해 구조를 지님

 

5. 완화

1) 현재 경로 값보다 더 적은 경로가 존재한다면 값을 변경

 

6. 벨만-포드 알고리즘

1) 하나의 시작점에서 하나의 도착점으로 가는 최단경로 문제를 Relax를 이용하여 순환문제를 회피, 해결하는 알고리즘

2) 음의 간선이 있는 경우에도 문제를 해결

3) 수행시간