👷🏻‍♂️수정 중...

Single Source Shortest Paths

그래프 $G = (V, E)$ 의 출발 정점 $s \in V$ 에서
각 정점 $v \in V$ 로의 최단 경로

최단 경로와 최단 경로 가중치의 정의

📍 가중치 함수 $\omega : E\to \R$
간선으로 실수값의 가중치를 구할 수 있는 함수

📍 경로 $p = <v_{0}, v_{1}, v_{2}, ..., v_{k}>$ 의 가중치는 그 경로를 이루는 간선들의 가중치 합

$\omega(p) = \sum_{i=1}^{k}\omega(v_{i-1}, v_{i})$

📍 $u\in V$, $v\in V$일 때, $u$에서 $v$까지 최단 경로 가중치 $\delta(u, v)$ 는 다음과 같다.

$\delta(u, v)$ = $\left\{\begin{matrix} & min\{\omega(p) : u\overset{p}{\rightarrow}v\}& : u에서 v까지의\ 경로가\ 존재할\ 경우 \\\\ & \infin & : 이외의\ 경우 \end{matrix}\right.$

📍 정점 $u$에서 $v$까지의 최단 경로(shortest path) 는
$\omega(p) = \delta(u, v)$를 갖는 경로 $p$ 로 정의된다.

최단 경로의 모든 부분 경로는 최단 경로이다.

그래프 $G =(V, E)$ 와 가중 함수 $\omega : E \to \R$ 이 주어졌을 때
$p = <v_{0}, v_{1}, v_{2}, ..., v_{k}>$ 를 정정 $v_{0}$에서 $v_{k}$ 까지의 최단 경로라고 하자,

$0\le i \le j \le k$ 인 $i$, $j$ 에 대해
$p_{ij} = <v_{i}, v_{i+1}, v_{i+2}, ..., v_{j}>$ 를 정점 $v_{i}$에서 $v_{j}$까지의 부분 경로라고 할 때,
$p_{ij}$는 $v_{i}$에서 $v_{j}$까지의 최단 경로이다.

유형

$G=(V, E)$ 에서

단일 출발지 최단 경로 문제 (Single-source)

출발 정점 $s \in V$에서 각 정점 $v \in V$로의 최단 경로를 찾는 문제

단일 도착지 최단 경로 문제 (Single-destination)

각 정점 $v \in V$에서 도착 정점 $t \in V$으로의 최단 경로를 찾는 문제.
간선의 방향을 모두 뒤집어 Single-source 문제로 바꿀 수 있다.

단일 쌍 최단 경로 문제 (Single-pair)

주어진 정점 $u$, $v$에 대해 $u$에서 $v$까지의 최단 경로를 찾는 문제.
문제 해결을 위해 알려진 모든 방법이 Single-source 문제의 worst case와 동일한 수행시간을 갖는다.

모든 쌍 최단 경로 문제 (All-pairs)

모든 정점 쌍 $u, v \in V$에 대해 $u$에서 $v$까지의 최단 경로를 찾는 문제.
Single-source 문제를 푸는 알고리즘을 각 정점에 대해 수행하며 풀 수도 있으나, 더 빠른 알고리즘이 존재함

단일 출발지 최단 경로 문제(Single-source)를 해결하는 방법에 대한 설명으로 위 유형에 대한 해결 방법을 제시할 수 있다.

순환 : 최단 경로는 순환을 포함할 수 없다.

• 가중치가 음수인 순환 : 음의 가중치를 갖는 순환을 여러번 반복하면 매우 큰 음의 가중치를 갖는 경로를 찾을 수 있고, 따라서 "최단" 경로를 찾을 수 없다.

• 가중치가 양수인 순환 : 출발지와 도착지가 같아, 더 작은 가중치를 갖는 경로를 만들기 때문에 불가능 하다.

• 가중치가 0인 순환 : 해당 간선을 이용할 이유가 없다.
  이 순환을 최단 경로로부터 제거하면 순환을 포함하지 않는 최단 경로를 구할 수 있다.
  즉, 일반성을 잃지 않고 최단 경로를 찾는 방법에서, 가중치가 0인 순환을 사용할 이유가 없다.

완화(Relaxation)

최단 경로 추정값(Shortest-path estimate)

완화 기술을 이용하기 위해서, 최단 경로 추정값 이라는 속성의 정의가 필요하다.

각 정점 $v \in V$ 에 대해,

• 초기값 $v.d = \infin$
• $v.d \ge \delta(s, v)$

을 유지하는 $v.d$ 를 최단 경로 추정값(Shortest-path estimate)이라고 한다.

즉, 정점 v로의 최단 경로를 구하는 과정에서 현재까지 구해진,
최단 경로로 '추정되는'값을 이야기 한다.

각 정점을 index로 하는 배열 또는 List로 구현 하거나
각 정점의 이름과 시작 정점으로 부터의 거리를 가진 class로 구현할 수 있다.

초기화

시작 정점으로 부터의 각 정점 $v \in V$에 대한 최단 경로 추정값은 모두 $\infin$로 초기화.
시작 정점$\to$시작 정점 의 최단 경로 추정값은 $0$으로 초기화.

완화

왜 완화(relaxation) 일까?
상한을 낮추어 $v.d \le u.d + \omega(u, v)$

간선 $(u, v)$를 완화하는 과정

• $u$에서 $v$까지의 최단경로 추정값 $v.d$의 개선 여부를 검사
• 개선 가능하다면, $v.d$ 갱신