Shortest path problem
📢 주어진 Graph에서 주어진 두 Node를 연결하는 가장 짧은 경로의 길이
📜 음수 간선
최단 경로 문제를 해결 할 때 가장 먼저 주의해야 하는 부분이에요. 바로 가중치 값이 음수를 가지는지 확인해야 해요.
만일 음수 간선이 존재한다면 음수 사이클이 존재할 수 있고, 위의 그림처럼 음수 사이클이 존재한다면 최단 경로를 찾을 수 없어요.
📜 최단 경로 알고리즘의 종류
- 다익스트라 알고리즘
- 벨만-포드 알고리즘
- 플로이드-워셜(Floyd-Warshall) 알고리즘
🔎 다익스트라(Dijkstra) 알고리즘
📢 우선 순위 큐를 사용해 각 Node까지의 최단 경로들을 구하는 알고리즘
- 우선 순위 큐에 (Node 번호, 지금까지 찾아낸 해당 Node까지의 거리)의 형태로 넣어요.
- 우선 순위 큐를 사용한다는 사실을 제외하면 BFS와 비슷한 방식을 가져요.
- 각 Node까지의 최단 경로가 갱신될 수 있음을 주의해야 해요.
- 음수 간선이 존재할 경우 잘못된 답을 얻을 수 있어요.
위의 그림을 보면서 설명할게요. s에서 출발하여 각 Node까지의 최단 거리를 구해볼거에요. 시작점에서 각 Node까지의 최단 거리를 나타내는 dist배열, 그리고 각 Node를 방문하면서 시작점에서 해당 Node까지 가는데 걸리는 길이를 cost라고 할게요.
- s와 인접한 Node(a, c)들을 우선 순위 큐에 넣어요. (a, 2) (c, 12)
- 그 중 짧은 거리를 가진 a를 방문해요.
- dist[a]를 2로 갱신하고, a에 인접한 Node b를 우선 순위 큐에 넣어요. (b, 6)
- 우선 순위 큐 내부 값들 중 가장 작은 cost 값 (b, 6)을 방문해요.
- dist[b]를 6으로 갱신하고, b에 인접한 Node c를 우선 순위 큐에 넣어요. (c, 9)
- 우선 순위 큐 내부 값들 중 가장 작은 cost 값 (c, 9)를 방문하고, dist[c]를 9로 갱신해요.
- 이때, s에서 c까지 가는 거리 길이는 dist[c]인 9와 우선 순위 큐 내부에 남아있는 (c, 12)가 있어요. 만일 이럴 경우에는 dist[c] < cost라면, c까지 가는 최단 경로를 찾았기 때문에 (c, 12)를 무시 하면 돼요. 반대라면 새로운 최단 거리를 발견한 것이므로 dist[c] 값을 갱신해요.
아래 예제를 통해 알고리즘 코드 올리도록 할게요.
📋 예제
백준 1753 - 최단경로
백준 1753 - 해답
백준 1238 - 파티
백준 1238 - 해답
🔎 벨만-포드(Bellman-Ford) 알고리즘
📢 각 정점까지 최단 거리의 상한을 적당히 예측한 뒤, 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여나가는 방식
- 각 정점까지의 최단 거리 상한을 담은 upper[] 배열이 있어요.
- 알고리즘이 종료될 때는 upper[]에 실제 최단 거리가 담겨있어요.
- 음수 간선이 있어도 최단 거리를 찾을 수 있어요.
- 음수 사이클이 존재하면 이를 우리에게 알려줘요.
- Node 개수를 N, Edge 개수를 E라고 했을 때 O(N * E)의 시간복잡도를 가져요.
초기에 우리가 아는 사실은 시작점 s에서 s까지의 거리는 0, 즉 upper[s] = 0 이라는 사실만 알아요. upper[s] = 0으로 초기화하고 나머지 값들은 아주 큰 수로 초기화 해요. 그 다음엔 아래의 특성들을 이용해 값을 찾아나가게 돼요.
📑 최단 거리 특성
dist[v] <= dist[u] + w(v, u) (dist[v]는 시작점에서 v까지의 최단 거리, w(v, u)는 v와 u사이의 거리)
🙅 dist[v] > dist[u] + w(v, u)는 성립하지 않아요
🎈 완화(Relax)
upper[u] + w(u, v) < upper[v] 를 이용해 upper[v]를 감소 시키는 과정
upper[u] >= dist[u] 입니다. upper배열은 해당 지점까지의 최단거리에 점점 가까워지는 배열이고 dist배열은 해당 지점까지의 최단거리 값을 가지고 있는 배열이니까요. 고로, upper[u] 값이 줄어든다면 upper[v] 값을 upper[u] + w(u, v)로 바꿔도 상관어요. 이 과정을 완화(Relax)라고 해요.
🤔 완화로 어떻게 최단 거리를..?
시작점 s에서 d까지의 최단 거리를 가는 경로가 위의 그림과 같다고 가정할 때 아래의 순서를 가져요.
1. upper[s] = 0이에요.
2, 모든 Edge들을 순회하면서 한 번씩 완화를 시도하면 (s, a)도 하나의 Edge이므로 완화가 되었어요.
3. 최단 거리 특성을 생각해보면 upper[a] <= upper[s] + w(s, a)가 성립해요.
4. 이때, upper[s] = 0이고 w(s, a)는 시작점에서 a까지의 최단거리를 나타내니까 upper[a] = w(s, a)가 성립 해요. 즉, upper[a]는 최단거리로 되었어요.
5. 이를 반복하게 되면 b, c, d가 최단 경로가 된다는 것을 알 수 있어요.
6. 모든 Edge을 한 번씩 완화하는 과정을 E - 1번 반복하면 최단 경로를 얻을 수 있어요.
🤨 음수 사이클 확인 방법
아까 위에서 모든 Edge를 한 번씩 완화하는 과정을 E - 1번 반복하면 된다고 했는데 이후에 한 번더 반복을 하면 돼요. 음수가 존재한다면 한 번 더 완화 하는 과정에서 더 작은 값이 존재하게 되므로 완화에 성공하게 돼요.
📋 예제
백준 11657 - 타임머신
백준 11657 - 해답
백준 1865 - 웜홀
백준 1865 - 해답
🔎 플로이드-워셜(Floyd-Warshall) 알고리즘
📢 음수 사이클이 존재하지 않을 때 모든 Node 간의 최단 경로를 구하는 알고리즘
🎈 경유점
위의 그림에서 u에서 v로 가는 경로가 있다고 가정해요. 이때 그 경로는 u와 v는 당연히 지나고 이를 제외한 다른 지점(B)을 또 지날 수도 있어요. 이렇게 경로가 거쳐가는 다른 지점을 경유점이라고 해요.
🤔 알고리즘을 표현해보자
집합 S에 임의의 Node들이 포함되어 있을 때, S에 포함된 Node만 사용하여 u에서 v로 가는 최단 경로가 존재한다고 가정해요. S 중에 아무 Node를 골라 x라고 한다면 최단 경로는 x를 경유하거나 안할 수 있어요. 이때 각각을 우리는 아래와 같이 표현할 수 있어요.
- 최단 경로가 x를 경유하지 않는다. -> x를 제외한 집합 S에 포함된 Node들만을 경유점으로 가진다.
- 최단 경로가 x를 경유한다. -> 경로(u -> x)와 경로(x -> v)로 나눌 수 있다. 이 또한 x를 제외한 집합 S에 포함된 Node들만을 경유점으로 가진다.
이를 점화식으로 나타내면 아래와 같이 표현 할 수 있어요.
(여기서 Ck(u,v)는 0번 Node부터 k번 Node까지만을 경유점으로 썼을 때 u에서 v까지의 최단 거리를 뜻해요.)
🎈 Dynamic Programming을 이용하자
단순히 위의 생각을 이용해서 코드를 구현하면 메모리가 부족해요. 그래서 실제로 알고리즘을 구현할 때는 DP를 사용해요. 시간 복잡도는 O()이에요.
📋 예제
백준 11403 - 경로 찾기
백준 11403 - 해답
백준 11404 - 플로이드
백준 11404 - 해답
