Shortest Paths - Bellman Ford, Dijkstra’s algorithm

MST와 Shortest Paths의 차이

https://guhonga.tistory.com/139

Minimum Spanning Tree (MST) 소개 - Kruskal, Prim’s algorithm

MST 소개 및 특징Spanning Tree란, cycle을 갖지 않고 그래프 내의 모든 정점이 연결된 트리를 말한다.n개의 vertex가 있는 Spanning Tree라면 n-1 개의 edge가 있다. 그렇다면 Minimum Spanning Tree (MST) 가 의미하

guhonga.tistory.com

앞에서 설명했던 MST 알고리즘은 그래프에서 모든 노드를 포함하면서, 사이클이 없고, 총 가중치의 합이 최소인 트리를 찾는 알고리즘이었다.

즉, 모든 노드를 연결하는 최소 비용의 트리를 찾는 알고리즘이다.

여기에서 더 나아간 Shortest Paths Algorithms은

모든 노드를 연결할 필요 없이, 그래프에서 두 노드 간의 가장 짧은 경로를 찾는 알고리즘이다.

Shortest Paths Algorithms은 다음과 같은 문제들로 구분할 수 있다.

주어진 source vertex에서 각 vertex까지의 최단 경로를 찾는 Single-Source Shortest-Paths (SSSP) Problem
각 노드에서 주어진 vertex까지의 최단 경로를 찾는 Single-Destination Shortest-Paths Problem
주어진 정점 쌍 (u, v) u에서 v까지의 최단 경로를 찾는 Single-Pair Shortest-Path Problem

Shortest Paths Algorithms 구조

Shortest Paths를 구성하기 위한 조건을 알아보자.

만약 가중치가 음수인 edge나 사이클이 있다면 어떻게 될까?

음수 가중치가 있는 edge 자체는 문제가 되지 않는다. 하지만 음수 가중치가 있는 사이클의 경우 문제가 된다.

이런 경우, 이 사이클을 여러 번 지나면서 경로 가중치를 무한히 줄일 수 있기 때문에 유의미한 최단 경로를 찾을 수 없다.

따라서 음수 가중치 사이클의 경로 가중치는 −∞에 수렴한다.

즉, 음수 가중치 사이클이 없는 경우에만 source vertext로부터 최단 경로를 정의할 수 있다.

반대로, 양수 가중치 사이클의 경우는 어차피 해당 경로를 개선하지 않기 때문에, 그냥 해당 사이클을 피하면 된다.

만약 vertex u에서 v까지 Shortest path를 구성하고 있다면, 해당 경로에 있는 u에서 x까지, x에서 y까지의 경로들도 또한 최단 경로이다.

이 이론은 다익스트라 알고리즘과 벨만 포드 알고리즘에서 중요한 기초 이론이다.

이를 기반으로 Single-Source Shortest-Paths (SSSP)에서 단순히 최단 경로의 가중치만 출력하는 것이 아니라, 최단 경로상의 정점들도 같이 출력하게 하자.

최단 경로상의 정점들도 출력하기 위해서 각 정점 v는

최단 경로 추정치 v.d
최단 경로에서의 predecessor v.π

이렇게 최단 경로의 추정치와 선행자를 관리하는 것으로, 전체 경로를 재구성할 수 있다.

SSSP 알고리즘은 일반적으로

초기화(Initialization) 단계와 완화(Relaxation) 단계로 나뉜다.

초기화 단계는 각 정점의 최단 경로 추정치와 선행자를 초기화시킨다.

INIT-SINGLE-SOURCE(G, s)
for each v ∈ G.V
    v.d = ∞
    v.π = NIL
s.d = 0

완화 단계는 모든 엣지 v.d 를 각 정점의 최단 경로 추정치로 업데이트한다.

RELAX(u,v,w)
if v.d > u.d + w(u,v)

	v.d = u.d+w(u,v)
	v.π = u

최단 경로의 주요 특징

삼각 부등식(Triangle Inequality):
- 모든 엣지 (u,v)에 대해 δ(s,v) ≤ δ(s,u) + w(u,v)가 성립한다.
  여기에서 δ(s,u)는 s에서 u까지의 최단 경로의 가중치를 말한다.
- 즉, u를 거쳐 v로 가는 경로는 s에서 v로 직접 가는 최단 경로보다 길지 않다.
상한 특성(Upper-Bound Property):
- 모든 정점 v에 대해 v.d ≥ δ(s,v)가 항상 성립한다.
  여기에서 v.d 는 현재 알고 있는 최단 경로 추정치이고, δ(s,v) 는 실제 최단 경로 가중치를 말한다.
- 즉, 초기에는 v.d 가 무한대일 수 있지만, 알고리즘이 진행됨에 따라 점차 줄어들어 δ(s,v) 에 도달하게 된다.
경로 완화 특성(Path Relaxation Property):
- 경로 p = ⟨v0,v1,…,vk⟩ 가 s=v0 에서 vk 까지의 최단 경로라면, 이 경로의 엣지들을 차례로 완화했을 때 vk.d = δ(s,vk) 가 된다.
- 즉, (v0,v1),(v1,v2),…,(vk−1,vk) 순서대로 엣지를 완화하면 최단 경로 추정치가 실제 최단 경로 가중치로 업데이트된다.

요약하자면

삼각 부등식은 최단 경로를 구할 때 중간 정점을 거치는 경로가 직접 경로보다 길지 않음을 보장한다.
상한 특성은 초기 추정치가 실제 최단 경로 가중치보다 크거나 같음을 나타낸다.
경로 완화 특성은 최단 경로 알고리즘의 작동 방식을 설명하며, 엣지를 반복적으로 완화하여 최단 경로 추정치를 업데이트하는 과정을 나타낸다.