개발 공부 - [그래프 알고리즘] 순회 - 최단경로(shortest path problem) - 1

최단경로

- 가중치 (방향) 그래프 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 처리 하도록 진행한다.