최단 경로 (1)

Shortest Path (1)

최단 경로

- 가중치(방향) 그래프 G = (V, E), 즉 모든 엣지에 가중치가 있다.

- 경로 p = $v_0$, $v_1$, ... , $v_k$)의 길이는 경로상 모든 엣지들의 가중치들 총 합이다.

- 노드 u에서 v까지의 최단 경로 길이를 δ(u, v)라고 표시한다.

최단 경로 문제의 유형

- Single-source (one to all)

하나의 출발 노드 s로부터 다른 모든 노드까지의 최단 경로를 찾는 문제.

Ex) Dijkstra algorithm

- Single-destination

모든 노드로부터 하나의 목적 노드까지의 최단 경로를 찾는 문제

single source와 본질적으로 거의 동일한 문제이다.

- Single-pair (실질적으로 가장 유용한 문제, one to one)

주어진 하나의 출발 노드 s부터 하나의 목적지 노드 t까지의 최단 경로를 찾는 문제

최악의 경우 시간 복잡도에서 single source문제보다 나은 알고리즘이 존재하지 않는다.

- All-pairs (all to all)

모든 노드 쌍에 대한 최단 경로를 전부 찾는 문제

Ex) Floyd algorithm

최단 경로와 음수 가중치

- 알고리즘에 따라서 음수 가중치가 있어도 작동하거나 작동하지 않거나 하는 경우가 나뉜다. 예를 들어 다익스트라 알고리즘은 음수 가중치가 존재하지 않는다고 가정하고 진행한다.

최단 경로의 기본 특성

- 최단 경로의 어떠한 부분 경로도 또한 최단 경로이다.

- 음수 사이클이 없다는 가정 하에 최단 경로는 사이클을 포함하지 않는다.

Single-source 최단경로 문제

- 입력 : 음수 사이클이 없는 가중치 방향그래프  G = (V, E)와 출발 노드 s ∈ V

- 목적 : 각 노드 v ∈ V에 대해서 아래의 절차를 계산한다.

1) d[v] (distence estimate, 현재까지 알고있는 s부터 v까지의 가장 짧은 길이)

d[s] = 0, d[v] = ∞으로 초기화된다.

알고리즘이 진행해감에 따라 점차 감소한다. 하지만 d[v] ≥ δ(s, v)를 항상 만족한 상태여야 한다.

최종적으로는 d[v] = δ(s, v)가 되며 알고리즘이 종료된다.

2) π[v] (s에서 v까지 최단경로 상에서 v의 직전 노드인 predecessor)

직전 노드가 없을 경우 π[v] = null이 된다.

기본 연산 : Relaxation

- 엣지에 대해 수행하는 연산. 왼쪽 그림에서 u노드의 값은 d[u]로 어떠한 노드로부터 u노드까지 오는 최단 길이가 5라는 것을 의미한다. relax 연산을 수행한 후 d[v]의 값은 (u, v)엣지의 길이인 2가 더해진 7이 된다.

- 오른쪽 그림의 경우 d[v]의 값인 6에 비해 d[u]에 (u, v)엣지의 길이인 2를 더한 값인 7이 더 크기 때문에 Relax 연산을 수행한다 하더라도 d[v]의 값이 갱신되지 않게 된다.

- 슈도 코드

RELAX (u, v, w) // w = weight 함수로 각 가중치들을 저장하고 있는 저장 구조를 의미한다.

if d[v] > d[u] + w(u, v)

d[v] = d[u] + w(u, v);

π[v] = u;

Single-source 최단 경로

- 대부분의 최단 경로 알고리즘은 relax연산을 반복적으로 수행함으로서 최단 경로를 찾게 된다.

초기화 : d[s](출발점) = 0, 노드 v ≠ s에 대해 d[v] = ∞, π[v] = null

모든 엣지들에 대해서 반복적인 relaxation 연산을 수행한다.

- 알고리즘들 간의 차이는 어떤 엣지에 대해 어떤 순서로 relaxation을 하느냐에 따라 다르다.

Single-source의 기본 알고리즘

Generic-Single-Source (G, w, s)

INITIALISE-SINGLE-SOURCE (G, s); // 초기화 작업

repeat until there is no change

for each edge (u, v) ∈ E

RELAX (u, v, w);

-> 반복을 몇번 수행해야 하는지와, 모든 노드에 대해 최단 경로가 찾아지는지에 대한 의문이 생길 수 있다.

-> n - 1번 반복하기만 한다면 모든 노드에 대해 최단 경로를 찾을 수 있게 된다.