최단경로
- 가중치 (방향) 그래프 G = (V,E), 즉 모든 에지에 가중치가 있음.
- 경로 p = (v0, v1, ... vk)의 길이는 경로상의 모든 에지의 가중치의 합
- 노드 u에서 v까지의 최단경로의 길이를 δ(u, v)라고 표시하자.
최단경로문제의 유형
- Single-source
: 하나의 출발 노드 s로부터 다른 모든 노드까지의 최단 경로를 찾아라.
- Single-destination
: 모든 노드로부터 하나의 목적지 노드까지의 최단 경로를 찾아라.
* single-source와 singled-destination은 사실상 같은 것으로 볼 수 있다.
- Single-pair
: 주어진 하나의 출발 노드 s로부터 하나의 목적지 노드 t까지의 최단 경로를 찾아라.
* 최악의 경우 시간 복잡도에서 Single-Source 문제보다 나은 알고리즘이 없을 수 있다.
- All-pairs
: 모든 노드 쌍에 대해서 최단 경로를 찾아라.
최단 경로와 음수 가중치
- 음수 가중치
: 가중치가 음수인 경우
- 음수 사이클이 있으면 최단 경로가 정의되지 않는다.
* 알고리즘에 따라 음수 가중치가 있어도 작동하는 경우도 있고, 그렇지 않은 경우도 있다.
최단 경로의 기본 특성
- 최단 경로의 어떤 부분경로도 역시 그 부분에 대한 최단 경로이다
* 전체 u~v에서, u에서 v까지의 최단 경로를 지정했을 떄,
중간 위치의 x~y 가 있다면 이 경로는 x에서 y까지의 최단경로이다.
- 최단 경로는 사이클을 포함하지 않는다.
( 음수 사이클이 없다는 가정 )
Single-source (one to all) 최단경로문제
- 입력 : 음수 사이클이 없는 가중치 방향그래프 G=(V,E)와 출발 노드 s ∈ V
- 목적 : 각 노드 v ∈ V에 대해서 다음을 계산한다.
- d[v]
- 처음에는 d[s]=0, d[v]=∞ 로 시작한다.
- 알고리즘이 진행됨에 따라서 감소해간다. 하지만 항상 d[v] ≥ δ(s,v)를 유지한다.
- 최종적으로는 d[v] = δ(s,v)가 된다.
- ㅠ[v]
: s에서 v까지의 최단경로상에서 v의 직전 노드 (predecessor)
- 그런 노드가 없을 경우 ㅠ[v] = NIL.
기본 연산 : Relaxation
기본 알고리즘
1. 초기화 진행
- 반복 -
2. 모든 에지들에 대해서 relax
- 3. 변화가 없으면 반복 종료 -
* 이렇게 반복 시에는 최단 경로가 찾아지는가?
* 몇 번 반복해야 하는가?
Bellman-Ford 알고리즘
: 기본 알고리즘과 초기화 하는 부분까지는 똑같은데,
변화 없을때까지 반복하는 것이 아니라,
반복 회수를 n-1번으로 고정해 놓고 진행한다.
* 음수 사이클이 존재할 때는 false 처리 하도록 진행한다.
댓글
댓글 쓰기