[알고리즘] ASP(2) - 최단경로와 행렬곱 ( Shortest Paths and Matrix Multiplication )

1. 최단경로와 행렬곱 ( Shortest Paths and Matrix Multiplication )

이번에는ASP의 첫 번째 알고리즘 최단경로와 행렬곱 알고리즘에 대해 알아보겠습니다.

최단경로와 행렬곱 알고리즘은 ASP를 행렬곱을 이용해서 구하는 것입니다.

실제로 행렬곱을 이용하지는 않고 행렬 곱셈의 연산방식을 따를 뿐입니다.

( 수식이 많아도 어렵지 않으니 천천히 읽어봐주세요 ! )

ASP를 구현할 때 인접행렬을 이용한다고 했죠?

위의 그림과 같이 두 개의 인접행렬이 있을 때 빨간 네모 부분(2행과 4열)을 곱하면 의 원소가 될 것입니다.

원래대로 행렬의 곱셈을 하면 아래의 식과 같습니다.

그런데 최단경로와 행렬곱 알고리즘은 행렬 곱셉 방식을 따를 뿐 실제로 행렬 곱셈연산을 하지는 않습니다.

최단경로와 행렬곱 알고리즘 방식으로 다시 식을 작성해보겠습니다.

따라서 의 값은 0이므로 v2 -> v4의 최단 경로의 비용은 0입니다.

2. 최단경로와 행렬곱의 동적 계획법 - 재귀적 해법

동적계획법의 재귀적 해법으로 표현해보겠습니다.

( 최단경로와 행렬곱 알고리즘은 동적 계획법을 사용합니다. )

: 정점 i에서 j까지의 최대 m개의 간선을 갖는 모든 경로의 최소 가중치 라고 정의하겠습니다.

예를 들어( i=3, j=2, m=2) 의 의미는 v3에서 v2까지 최대 2개의 간선을 갖는 모든 경로 중 가중치가 가장 작은 것을 의미합니다.

최대 2개라고 했으므로 1개의 간선 또는 2개의 간선을 거쳐갈 경우를 생각해 볼 수 있네요.

1) 1개의 간선을 거쳐갈 경우 (직접 연결될 경우)

v3 -> v2로 직접 연결된 간선이 있고, 이 때의 가중치는 4입니다.

2) 2개의 간선을 거쳐갈 경우

v3 -> ? -> v2 에 해당하는 간선이 존재하지 않습니다.

따라서 의 값은 4입니다.

이제 이를 좀 더 수학적으로 표현해보겠습니다.

식이 어려워 보일 수 있는데 처음에 봤던 행렬 곱셈 방식을 식으로 정리한 것 뿐입니다.

는 인접행렬 의 이전 단계를 의미합니다.

는 k가 1부터 n( 정점의 개수 )까지에 대해서 인접행렬 (가중치 인접행렬) 의 행렬곱 방식을 수행한 것입니다.

위의 두 식을 계산한 후 최소 값이 이 됩니다.

방금 위의 예제에서 ( i=3, j=2, m=2)을 구할 때를 생각해볼게요.

맨 처음 행렬 곱 방식을 했던 것과 완전히 같습니다.

최단경로와 행렬곱 알고리즘은 이러한 원리로 구현됩니다.

지금까지 봤던 알고리즘에 비해서 꽤 복잡해보입니다.

그 이유는 식을 주저리 주저리 써놓아서 그런 것 뿐이지, 과정을 보시면 그리 어렵지는 않을 것입니다.

3. 최단경로와 행렬곱 알고리즘

그래프가 주어졌을 때 이를 인접행렬로 표현하면 위와 같습니다.

그리고 인접행렬 는 위의 관계를 따릅니다.

즉 이며, 정점의 개수가 5개이므로 를 구하는 것이 목표입니다.

( m은 최대 간선의 개수를 의미하므로 정점의 개수를 넘지 못합니다.)

이제 앞에서 살펴봤던 재귀적 해법을 이용하여 까지 구해보겠습니다.

를 구하면 다음과 같습니다.

i , j 를 정해놓고 k를 움직이면서 위의 식에 대입하면 결과를 얻을 수 있습니다.

행렬의 곱셈 연산의 방식을 이용하고 재귀적 해법의 식에 적절히 i , j , m , k 값을 대입하면 어렵지 않게 구할 수 있습니다.

4. 수도코드

1) SLOW-ALL-PAIRS-SHORTEST-PATHS 함수

line 3 ~ 5

m은 2부터 최대 n-1까지 Bottom-up(상향식) 방식으로 인접행렬 을 구합니다.

예를들어 정점의 개수가 5라면 까지 구하고 종료될 것입니다.

2) EXTEND-SHORTEST-PATHS 함수

line 3 ~ 7

변수 i , j는 각각 행과 열을 의미합니다.

그리고 변수 k는 1부터 n까지 움직이는 값으로써 재귀적 해법의 식을 수행합니다.

3) 시간복잡도

SLOW-ALL-PAIRS-SHORTEST-PATHS 함수에서 EXTEND-SHORTEST-PATHS 함수를 호출했습니다.

따라서 총 4번의 중첩 for문이 발생했으므로 시간 복잡도는 이 됩니다.

그런데 ASP를 소개할 때 Bellman-Ford 알고리즘과 Dijkstra's 알고리즘의 성능이 좋지 않아서 ASP를 구현한다고 했는데, 최단경로와 행렬곱 알고리즘은 성능이 그닥 좋지 못합니다.

그래서 이를 좀 더 개선한 방법이 있습니다.

이 글에서는 왼쪽의 방식으로 최단경로와 행렬곱 알고리즘을 소개했습니다.

그런데 이 구현을 오른쪽과 같이 수정하면 시간 복잡도를 만큼 줄일 수 있습니다.

왜냐하면, 의 크기로 증가하기 때문입니다.

이에 대한 수도코드는 아래와 같습니다.

이상으로 최단경로와 행렬곱 알고리즘에 대해 알아보았습니다.

수식이 많아서 글이 많이 어지럽네요.

사실 동작 과정과 구현은 그리 어렵지 않은데 말이죠...