최단 경로 문제

최단 경로 문제

최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제다.

가중치가 있는 그래프(Weighted Graph)에서는 Edge의 가중치의 합이 최소가 되도록 하는 경로를 찾으려는 것이 목적이다.

최단 경로 문제에는 다음과 같은 유형이 있다.

 

• 단일 출발 최단 경로: 단일 노드 𝑣에서 출발하여 그래프 내의 모든 다른 노드에 도착하는 가장 짧은 경로를 찾는 문제
• 단일 도착 최단 경로: 모든 노드들로부터 출발하여 그래프 내의 단일 노드 𝑣로 도착하는 가장 짧은 경로를 찾는 문제. 단일 출발 최단 경로를 거꾸로 뒤집은 것과 같다.
• 단일 쌍 최단 경로: 주어진 꼭짓점 𝑢와 𝑣에 대해 𝑢에서 𝑣까지의 최단 경로를 찾는 문제
• 전체 쌍 최단 경로: 그래프 내 모든 노드 쌍들 사이의 최단 경로를 찾는 문제

다익스트라, 벨만-포드 알고리즘은 여기서 단일 출발 최단 경로 문제(우리가 흔하게 생각하는 최단 경로 문제)를 푸는 데에 적합하다.

 

 

Optimal Substructure

최단 경로의 중요한 속성이 있다.

다익스트라 알고리즘이나 벨만-포드 알고리즘이 최단 경로를 찾을 때 써먹는 핵심 정리이기도 하다.

 

 

최단 경로의 부분 경로는 역시 최단 경로이다.

 

예를 들어 아래 그림을 보자.

직선은 엣지, 물결선은 경로를 나타낸다.

엣지 가중치 합이 최소인 최단 경로는 굵게 표시된 첫번째 경로임을 알 수 있다.

그러면 시작 노드부터 중간 노드(가중치가 5) 또한 최단 경로이다.

 

위 정리를 증명한 내용은 다음과 같다.

 

p를 𝑢와 𝑣의 최단 경로라고 가정하자.

최단 경로의 거리 = p의 가중치 = 𝑢와 x의 엣지 p 가중치 + x와 y의 엣지 p 가중치 + y와 𝑣의 p 가중치

만약 x부터 y까지의 경로에 p'라는 더 짧은 경로가 존재한다고 가정하자.

 

그러면

p'의 가중치 = 𝑢와 x의 엣지 p 가중치 + x와 y의 엣지 p' 가중치 + y와 𝑣의 p 가중치 

< 𝑢와 x의 엣지 p 가중치 + x와 y의 엣지 p 가중치 + y와 𝑣의 p 가중치

= 엣지 p의 가중치

 

이는 p가 최단 경로라는 가정과 모순된다.

 

위 정리를 확장하면 최단 경로를 다음과 같이 분해(Decomposition)할 수 있다.

 

시작노드 𝑠에서 𝑣에 이르는 최단경로는 𝑠에서 𝑢까지의 최단경로에 𝑢에서 𝑣 사이의 가중치(거리)를 더한 값이라는 것이다.

 

 

𝐷(𝑠,𝑣)=𝐷(𝑠,𝑢)+𝑤(𝑢,𝑣)

만약 우변이 좌변보다 작다면 최단 경로를 업데이트해야 한다.

이렇게 노드별로 하나씩 확장해 나가면  𝑠에서 𝑣 사이의 최단 경로를 구할 수 있다.

 

이와 같이 어떤 문제의 최적 해가 그 부분 문제들의 최적 해로 구성될 수 있다면 해당 문제는 Substructure을 가진다고 말한다.

Dynamic Programming, Greedy Algorithm을 적용해 문제를 풀 수 있다.

 

Edge Relaxation

최단 경로를 구하는 알고리즘은 Edge Relaxation(변 경감)을 기본 연산으로 한다.이는 지금까지 이야기한 최단 경로 문제의 Optimal Structure에서 파생된 것이다.

 

우선 시작 노드 𝑠에서 임의의 노드 𝑧로의 최단 경로를 구한다고 친다.그리고 현재 시점에서 우리가 알고 있는 𝑠, 𝑧 사이의 최단 거리 𝑑(𝑧)는 75, 𝑠,𝑢 사이의 최단거리 𝑑(𝑢)는 50이라고 한다.

 

그런데 탐색 과정에서 엣지 𝑒를 경유하는 경로의 거리가 총 60이면, 기존에 우리가 알고 있는 𝑑(𝑧)가 최단 경로라고 말할 수 없게 된다.이에 최단 경로를 구성하고 있는 노드와 엣지 정보, 그리고 거리의 합을 업데이트 해준다.이것이 바로 Edge Relaxation이다.

 

Edge Relaxation은 최단 경로 알고리즘을 수행하는 과정에서 경로를 구성하는 엣지 가중치의 합을 줄여나간다는 취지로 이런 이름이 붙은 것이다.

 

알고리즘 특성별 비교(feat. Bellman-Ford vs. Dijkstra)

최단 경로 알고리즘은 크게 다익스트라와 벨만 포드 알고리즘이 있다.

다익스트라 알고리즘은 엣지 가중치가 음수일 경우 동작하지 않는다.

벨만-포드 알고리즘의 경우 엣지 가중치가 음수여도 동작하나 negative cycle(음의 값이 누적되는 사이클)이 있으면 동작하지 않는다.

 

시간 복잡도

다익스트라의 시간복잡도는 𝑂(|𝑉|^2+|𝐸|)

벨만-포드의 시간복잡도는 𝑂(|𝑉||𝐸|)

 

앞서 말한 단일 지점 위주의 경로 찾기 외에 전체 쌍 최단 경로 문제에는 Floyed-Warshall 알고리즘이 널리 쓰인다.

최단 경로의 optimal substructure를 활용한 것으로 pseudo code는 다음과 같다.

 

단일쌍 최단 경로 문제는 서로 독립적이기 때문에 최근엔 단일쌍 문제 풀이에 적합한 다익스트라/벨만포드 알고리즘을 GPU를 활용해 병렬 처리하는 방식으로 전체 쌍 최단 경로를 푸는 경우가 많다고 한다.

 

참고

https://ratsgo.github.io/data%20structure&algorithm/2017/11/25/shortestpath/

최단 경로 문제 · ratsgo's blog

https://ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/

벨만-포드 알고리즘 · ratsgo's blog

https://ratsgo.github.io/data%20structure&algorithm/2017/11/26/dijkstra/

다익스트라 알고리즘 · ratsgo's blog