[Algorithm] 최단 경로

최단 경로

최단 경로란 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 문제로, 그래프의 응용문제 가운데 가장 유용하고 널리 사용된다. 가중치가 없는 그래프에 대한 최단 경로는 너비 우선 탐색(Breadth First Search)을 통해 구할 수 있지만, 가중치가 있는 그래프에 대해서는 좀 더 복잡한 방법이 필요하다.

 

음수 사이클

최단 경로 문제를 해결하기 위해 가장 유의해야 하는 부분은 음수 가중치를 갖는 간선이 있는지다. 음수 간선이 존재하는 그래프에서 해당 간선을 지나가면 전체 경로의 길이가 짧아지게 된다. 이러한 특성에 더해 만약 가중치에 합이 음수인 사이클이 그래프에 존재한다면, 최단 경로의 길이는 음의 무한대까지 발산하게 된다. 그러므로 음수 사이클이 있는 그래프에서는 어떤 최단 경로 알고리즘도 정확하게 최단 경로를 구할 수 없으며, 단지 알고리즘에 따라 음수 사이클의 존재 여부 정도만 확인해 줄 수 있다.

 

단일 시작점에 대한 최단거리와 모든 쌍에 대한 최단거리

최단 경로를 구함에 있어서 고려해야 하는 또 다른 중요한 내용은, 알고리즘이 단일 시작점에 대해 동작하는지 아니면 모든 쌍에 대해 동작하는지이다. 단일 시작점 최단 거리 알고리즘(Single Source Shortest Path, SSSP)들은 한 정점으로부터 모든 정점에 대한 최단 거리를 구하고, 모든 쌍 최단 거리 알고리즘(All Pair Shortest Path, APSP)들은 시간복잡도는 조금 더 크지만 모든 정점으로부터 모든 정점에 최단 거리 구할 수 있다. 물론 단일 시작점 알고리즘을 모든 단일 시작점들에 대해 수행한다면 모든 쌍에 대한 최단 거리를 구할 수 있겠지만, 그 방법으로는 모든 쌍 최단 거리 알고리즘보다 성능적으로 비효율적이므로 상황에 맞게 적절한 알고리즘을 선택하는 것이 중요하다.

 

기반 그래프

최단 경로 알고리즘들이 동작하는 그래프는 모든 방향 그래프를 포함한다. (다중 그래프도 포함한다) 만약 무향 그래프에 대해 최단 경로를 찾고자 한다면, 각각의 양방향 간선을 두 개의 방향 간선으로 분리하여 방향 그래프로 표현해야 한다. 하지만 음수 가중치를 포함하는 무향 그래프에서는 음수 무향 간선 하나로 음수 사이클이 만들어지기 때문에 어떤 상황에서도 최단 거리를 구할 수 없다. 음의 가중치를 갖지만, 음의 사이클은 갖지 않는 방향 그래프에서는 알고리즘의 특성에 따라 잘 동작하는 알고리즘도 있고 그렇지 않은 알고리즘도 있다.

 

다익스트라 알고리즘

다익스트라(Dijkstra) 알고리즘은 가장 유명한 그래프 최단 경로 알고리즘으로 단일 시작점으로부터 모든 정점에 대한 최단 거리를 생성해준다. 단, 간선은 음수 가중치를 갖지 않는다는 전제가 있어야 한다. 시간복잡도는 어떻게 구현하느냐에 따라 다르겠지만, 일반적으로는 O(E x logV)의 시간에 동작한다. (E : 간선의 개수, V : 정점의 개수)

다익스트라 알고리즘의 탐색 과정은 정점을 탐색 완료된 정점 집합과 미 탐색 정점 집합으로 구분하여 진행한다. 탐색 과정에 필요한 자료구조는 다음과 같다.

// 각 정점까지의 최단거리, 초기값으로 모든 정점을 무한대로 세팅한다.
vector<int> distances(graph.size(), numeric_limits<int>::max());

// (정점, 거리)을 저장하는 Dist 구조체 정의
// 거리 기준으로 정렬되는 우선순위큐 정의
priority_queue<Dist> pq;

다익스트라 알고리즘은 탐색대상 정점들을 탐색 완료된 정점 집합, 탐색대상 정점 집합, 미 탐색 정점 집합으로 구분한다. 우선순위 큐를 기준으로 보면 탐색 완료된 정점 집합은 우선순위 큐에 들어갔다가 나온 정점들을 의미하고, 탐색대상 정점 집합은 우선순위 큐에 들어가 있는 정점들을 의미하며, 미 탐색 정점 집합은 아직 우선순위 큐에 들어가지 않은 정점들을 의미한다. 먼저 초기 정점 s를 우선순위 큐에 넣고 이 정점으로부터 연결된 모든 정점을 (정점, 정점까지의 거리) 쌍으로 탐색대상 정점 집합에 포함한다. 또한 이 과정에서 각 정점에 대한 거리도 갱신한다. 그 후 탐색대상이 된 정점 중 해당 정점까지의 거리가 가장 짧은 정점들부터 큐에서 나오게 된다. 한번 큐에서 빠져나온 정점은 탐색 완료된 정점으로 이때의 거리는 최단 거리가 된다. (물론 이 이후에도 같은 정점에 대해 다른 거리로 큐에서 빠져나오게 되는데 이 정점들은 무시한다. 자세한 설명은 동작 과정에 있음) 다시 빠져나온 정점들을 대상으로 앞에서와같이 연결된 모든 정점을 탐색대상 정점 집합에 포함한다. 이 과정을 루프를 통해 우선순위 큐가 비어있을 때까지 반복한다.

 

동작과정

다음 그래프를 통해 실제 동작 과정을 살펴보자.

가운데가 탐색 대상 방향 그래프이고, 아래가 각 정점까지의 거리를 저장할 dist 배열, 오른쪽이 우선순위 큐의 상태를 보여준다. 먼저 초기 정점인 0까지의 거리를 0으로 세팅하고, (정점, 거리) 쌍을 우선순위 큐에 넣는다.

 

 

먼저 0번 정점을 방문한다. 우선순위 큐에서 0번 정점을 꺼내고, 0과 연결된 모든 정점까지의 거리(dist[1], dist[2])들을 갱신하고,  (정점, 거리) 쌍을 우선순위 큐에 넣는다. 각 정점까지의 거리는 현재까지의 거리 + 간선의 가중치로 계산된다.

// 1번 정점까지의 거리
dist[1] = dist[0] + graph[0][1]

// 2번 정점까지의 거리
dist[2] = dist[0] + graph[0][2]

그 후, 0번 정점은 우선순위 큐에서 제거되고 이제 탐색 완료 정점으로 분류된다.

 

 

 

 

다음으로 거리가 최소인 2번 정점을 우선순위 큐에서 꺼낸다. 그리고 2번 정점으로부터 연결된 1번 정점까지의 거리 dist[1]를 갱신하고 큐에 (1, 3)을 넣는다. 1번 정점은 아직 우선순위 큐 안에 있는 정점이기 때문에 탐색 완료된 정점으로 분류되지 않는다. 그러므로 아직 거리가 갱신될 여지가 남아있다고 볼 수 있고, 이 경우도 더 짧은 최소거리인 3으로 갱신된다. 다만 이 경우 dist에서의 최소거리는 갱신되었지만, 아직 우선순위 큐 내의값은 (1, 4)라는 업데이트되지 않은 데이터가 남아있는 문제가 생긴다. 이 문제를 해결하기 위해 후에 일단은 (1, 4)를 그대로 두고 이후 큐에서 꺼내질 때, dist[1]와 비교하여 더 작다면 무시하는 형태로 구현할 수 있다. 이러한 방법으로 구현한 다익스트라를 레이지 다익스트라(Lazy Dijkstra)라 부른다.

 

 

3번 정점까지의 거리를 갱신, (3, 6)을 큐에 넣고 2번 정점을 큐에서 제거한다. 2번 정점도 탐색완료 정점으로 분류된다.

 

 

다음으로 1번정점을 큐에서 꺼낸 후 똑같이 진행한다. dist[3]을 기존값 6에서 더 최단거리인 4로 갱신시키고 (3, 4)를 큐에 넣는다. 그 후, 1번 정점을 큐에서 제거한다.

 

 

다음으로 이전에 넣어두었던 1번 정점까지의 거리 (1, 4)가 큐에서 꺼내게 되는데, 이미 1번 정점까지의 거리는 3이라는 최단 거리로 확정된 상태이다. 그러므로 이 데이터는 무시하도록 한다.
여기서 이후에 들어온 데이터가 이전에 확정된 데이터보다 최단 거리를 가질 수 있지 않나? 라는 의문을 품을 수 있다. 하지만 큐에 넣어지는 순서는 최단이 아니더라도 먼저 들어갈 수 있지만, 큐에서 나오는 순서는 해당 정점까지의 최단 거리 순서로 나오기 때문에, 만약 더 최단인 정점이었다면 큐에서 먼저 꺼내졌어야 한다. 이것은 증명은 귀류법으로 증명이 가능한 내용이다.

 

 

다음으로 3번 정점에 대해서 똑같이 수행한다.

 

 

그 후 이전에 큐에 넣어두었던 (3, 6) 데이터를 무시한다.

 

 

마지막으로 4번 정점까지 방문하고 다익스트라 알고리즘이 마무리된다.

 

 

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/ShortestPath/1-Dijkstra.cpp

insooneelife/AlgorithmTutorial

 

정당성 증명

다익스트라 알고리즘은 최단 거리가 확정된 정점 집합으로부터 뻗어 나가는 모든 간선 중 최소의 가중치를 갖는 간선을 선택하는 것이 최적이라는 것을 전제로 하고 있다. 이것은 귀류법으로 증명이 가능하다.
먼저 다익스트라 알고리즘이 최단 거리를 제대로 계산하지 못하는 정점 U가 있다고 가정한다. 다만 시작점에 대해서는 항상 정확하게 최단 거리를 계산할 수 있으므로, U는 시작점이 될 수 없다는 사실을 알 수 있다. 그러면 다익스트라 알고리즘이 U를 방문하는 순간 U 이전에 방문한 정점들과 아직 방문하지 않은 정점들로 그래프를 나눌 수 있다. 이때 다익스트라 알고리즘이 U를 잘못 계산했다는 것은 현재까지 방문 된 정점들로부터의 경로보다 더 짧은 경로가 존재한다는 의미이다. 아래 그림은 다익스트라 알고리즘의 탐색 과정을 현재까지 방문 된 정점 집합(다익스트라 스패닝 트리)과 방문 되지 않은 정점 집합으로 구분한다. 다익스트라로 계산된 최단 경로는 파란색 간선으로 끝나는데, 귀류법으로 그보다 더 최단인 어떤 경로가 존재할 것이라고 가정했기 때문에 그 경로를 붉은색 점선으로 표시하였다. U로부터 점선 경로를 역으로 따라가다 보면 결국 이미 방문한 어떤 정점 P를 만나게 될 것이다. 그 직전 정점은 Q라고 하자. 이때 시작점으로부터 Q까지의 최단 거리는 dist[P] + graph[P][Q]이다. 하지만 P는 이미 방문한 상태이기 때문에, dist[Q]는 값이 갱신되어 있을 것이고 Q는 우선순위 큐에 들어가 있을 것이다. 현재까지의 가정은 다익스트라 알고리즘이 U정점을 방문하는 순간을 전제로 하고있다. 즉, Q와 U가 모두 우선순위 큐에 들어가 있는 상태에서 U가 먼저 큐에서 꺼내졌다는 의미이고 dist[U] <= dist[Q]임을 알려준다. 이는 Q를 거쳐서 U로 오는 경로가 dist[U]보다 짧다는 가정의 모순이다. 그러므로 다익스트라 알고리즘으로 찾는 경로가 항상 최단 경로라는 결론을 얻을 수 있다. (단 간선의 가중치가 음수가 아니라는 전제가 있어야 한다.)

 

 

 

 

 

 

벨만 포드

TODO

 

플로이드

플로이드 워셜(Floyd-Warshall) 알고리즘은 대표적인 모든 쌍 최단 거리 알고리즘이다. 물론 단일 정점 최단 거리 알고리즘을 이용하더라도 모든 쌍에 대한 최단 거리를 얻을 수 있다. 모든 정점을 시작점으로 총 V 번 알고리즘을 수행하면 될 것이다. 예를 들어 다익스트라를 모든 정점에 대해 수행해본다면 O(V x E x logV)의 수행시간을 갖을 것이다. 하지만 플로이드 알고리즘을 이용한다면 이보다 훨씬 효율적인 알고리즘을 작성할 수 있다. 또한 플로이드 알고리즘은 음의 사이클이 아니라면 음의 가중치를 갖는 간선이 존재하더라도 최적의 해를 구해낼 수 있다. 시간복잡도는 어떻게 구현하느냐에 따라 다르겠지만, 일반적으로는 O(V^3)의 시간에 동작한다. (E : 간선의 개수, V : 정점의 개수)

 

플로이드 알고리즘은 동적 계획법을 이용하여 구현할 수 있다. 이 동적 계획법의 아이디어는 어떤 정점 u에서 v로 갈 때의 최단 경로를 조금 더 구체적으로 설명하는 방법으로 부분 문제를 정의한다. 즉 u에서 v로 가는 최단 경로는 단순한 u->v 간선 하나만 거쳐서 도달하는 경우도 있겠지만, 어떤 경유 점들을 거쳐서 도달하는 경우도 있을 것이다. 그러므로 그 중간 경유 점들을 활용하여 점화식을 설계할 수 있다. 먼저 다음과 같이 필요한 개념들을 정의한다.

S : 정점 집합
x : 정점 집합 내의 어떤 한 정점
D(S, u, v) : S에 있는 정점들만을 경유점으로 하여 u로부터 v까지 이동하는 최단경로의 길이 (경유점은 이용하지 않아도 된다.)

 

다음과 같은 그래프를 생각해보자.

여기서 D(S, u, v)의 예시는 다음과 같다.

D({}, 0, 1) = 5
D({}, 3, 4) = 4
D({2, 3}, 0, 1) = 4
D({0, 2, 3, 4, 5, 6}, 1, 5) = D({}, 1, 5) = 3

 

D(S, u, v)를 구하기 위해서는 다음과 같이 두 가지 경우로 나누어 생각해볼 수 있다.
1. x를 경유하지 않는 경우

이 경로는 S - {x} 에 포함된 정점들만을 경유점으로 사용하여 u -> v로의 최단거리를 구한다.

D(S, u, v) = D(S - {x}, u, v);

 

2. x를 경유하는 경우

이 경로는 u -> x로 가는 경로와 x -> v로 가는 경로로 나눌 수 있다. 이 부분 경로들도 x를 경유하지 않기 때문에 S - {x} 에 포함된 정점들만을 경유점으로 이용한 최단거리를 구한다.

D(S, u, v) = D(S - {x}, u, x) + D(S - {x}, x, v);

 

D(S, u, v)는 위 두 경우 중 더 짧은 경로가 될 것이다. 재귀적으로 다음과 같이 정의할 수 있다.

S' : S - {x}, 정점 집합에서 x 정점만 제외한 정점 집합
D(S, u, v) = min(D(S', u, x) + D(S', x, v), D(S', u, v))

 

 

여기까지 정의된 점화식을 이용하면 집합에서 어떤 원소 x를 경유점으로 할 때의 최적해를 구할 수 있다. 물론 재귀적으로 점화식이 부분문제들에 대해 처리되면서 x의 값이 계속 변하겠지만, x의 값이 순차적으로 감소하는 형태가 좀 더 구현하기 용이할 것이다. 그러므로 이 점화식을 추상적인 x에 대한 점화식이 아니라 선형적으로 나열된 {}, {1}, {1, 2}, {1, 2, ..., k} 집합들에 대해서 처리가 가능하도록 다시 설계할 수 있을 것이다. 다음과 같이 모든 k개의 원소를 갖는 S를 이용하도록 점화식을 확장한다.

S(k) : {0, 1, ..., k} 를 원소로 하는 집합
C(k, u, v) : S(k)을 경유점으로 썼을 때 u에서 v까지 가는 최단경로의 길이
C(k, u, v) = min(C(k - 1, u, k) + C(k - 1, k, v), C(k - 1, u, v));

 

구현

이제 이 점화식을 직접 구현해보자. 다음과 같은 순서대로 구현할 수 있을 것이다.
1. 동적 계획법을 효율적으로 구현하기 위해 인접 행렬 그래프를 이용한다.
2. 그래프에서 간선이 없는 경우 0 대신 양의 무한대 값을 넣는다.
3. u = v인 경우 최단 거리를 0으로 세팅한다.
4. 동적 계획법을 적용할 3차원 배열 dp[V][V][V]를 잡는다. 이는 {0, 1, ... k}의 정점을 경유점으로 하는 u로부터 v까지의 최단 거리를 dp[k][u][v] 위치에 저장하기 위한 배열이다.
5. k = 0일 때의 기저값을 세팅한다.
6. 점화식을 적용한다.

 

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/ShortestPath/3-Floyd.cpp

insooneelife/AlgorithmTutorial

 

하지만 이 구현대로라면 정점이 많아지는 경우 너무 많은 메모리를 사용하게 된다. 메모리를 줄이기 위해 이 점화식을 조금 더 최적화시켜보자. 반복문에서 점화식의 형태는 다음과 같다.

dp[k][u][v] = min(dp[k - 1][u][v], dp[k - 1][u][k] + dp[k - 1][k][v]);

여기서 k번째 모든 (u, v)에 대한 최적해를 구하기 위해서는 k - 1번째 모든 (u, v)에 대한 최적해만 있으면 된다는 사실을 알 수 있다. 그러므로 굳이 k개의 2차원 배열을 들고 있을 필요가 없이 이전 배열만 알고 있으면 된다. 그리고 바로 이전 배열의 경우 굳이 한 벌 더 갖고 있을 필요 없이, 현재 배열을 재활용할 수 있다.

dp[u][v] = min(dp[u][v], dp[u][k] + dp[k][v]);

 

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/ShortestPath/4-Floyd-Memory-Optimize.cpp

insooneelife/AlgorithmTutorial

 

경로 생성

플로이드 알고리즘을 활용해서 모든 정점 쌍에 대한 최단 거리를 얻을 수 있다. 하지만 실제 문제에서는 최단 거리 뿐만 아니라 실제 경로를 계산해야 하는 상황도 생길 수 있다. 최단 경로를 얻기 위해 최단 거리를 구하는 과정에서 최적해에 대한 중간 경유점들을 저장해 둘 필요가 있다. 이 경유점들을 이용하면 최단 경로를 생성할 수 있다.
예를 들어 중간경유점을 via[V][V] 라는 테이블에 저장한다고 해보자. dp[u][v]의 최적해가 구해진 시점에서 어떤 정점 w가 via[u][v]에 저장되었다는 것은 u->v의 최단 거리는 w를 경유한다는 의미이다. 그러므로 재귀 호출을 이용하여 u->w로의 최단 경로를 찾고, w->v로의 최단 경로를 찾은 뒤 둘을 합친다면 u->v로의 최단 경로를 얻을 수 있다.

 

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/ShortestPath/5-Floyd-Make-Path.cpp

insooneelife/AlgorithmTutorial

 

 

 

간선 추가 및 최단거리 갱신

플로이드 알고리즘을 이용하여 최단 거리 테이블을 얻었다고 하자. 하지만 만약 이 상태에서 그래프에 간선이 추가된다면 어떤 문제가 생기게 될까? 추가된 간선을 이용하여 이동할 때 더 최단이 경로를 얻을 수 있다면 이 테이블은 갱신되어야 할 것이다. 가장 단순하게는 추가된 간선까지 포함하여 처음부터 다시 플로이드 알고리즘을 이용하여 새로운 최단 거리 테이블을 만들 수 있을 것이다. 하지만 간선이 지속해서 추가되는 상황이라면 이와 같은 방법은 너무 비효율적이다.
플로이드 알고리즘의 동작 원리를 알고 있다면 플로이드 알고리즘을 전부 돌리는 대신 일부만을 수행하여 테이블을 갱신시킬 수 있다. 먼저 간선의 경우 방향 정보를 갖고 있기 때문에 기존 정점을 이용하여 정의된 점화식으로는 구분하지 못하는 상황이 생기게 된다. 그러므로 현재의 점화식을 간선을 이용한 점화식으로 다시 구성하도록 한다.

E : 간선 집합
e(a, b) : 간선 집합의 어떤 한 간선 (a 정점 -> b 정점)
E' : E - {e(a, b)}, E에서 e(a, b)를 뺀 간선 집합
D(E, u, v) : E에 포함된 간선을 경유하며 u에서 v로 가는 최단 거리

양방향의 경우
D(E, u, v) = min(
    D(E', u, v), 
    D(E', u, a) + e(a, b) + D(E', b, v),
    D(E', u, b) + e(b, a) + D(E', a, v));
    
단방향의 경우
D(E, u, v) = min(
    D(E', u, v), 
    D(E', u, a) + e(a, b) + D(E', b, v));

 

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/ShortestPath/6-Floyd-Edge-Update.cpp

insooneelife/AlgorithmTutorial

 

 

이미지 출처 (https://github.com/williamfiset/Algorithms)