[computer science] all-pair shortest path(2) (Floyd-Warshall Algorithm, Johnson Algorithm)

이 게시글은

서울대학교 데이터사이언스대학원

조요한 교수님의

데이터사이언스 응용을 위한 컴퓨팅 강의를

학습을 위해 재구성하였습니다.

---

이번 시간은 apsp의 두번째 강의 내용을 정리해보려고한다

내용은 Floyd-Warshall Algorithm과

Johnson Algorithm이다

 

Floyd-Warshall Algorithm

 

Floyd-Warshall Algorithm의 가정은 아래와 같다

negative weight는 존재하지만 negative weight cycle은 존재하지 않는다

 

time complexity는 O(V세제곱)이 소요되고

dynamic programming(dp)를 이용해서 해결하는 알고리즘 중 하나이다

 

최적해를 찾는 구조를 살펴보자

우선 그래프G가 있다고 할 때 모든 vertex들을

1부터 n까지 numbering을 해준다

 

그러고 d라는 변수를 정의해줄건데 이게 어떤 변수냐하면

i에서 j까지 가는 shortest path의 거리인데,

1부터 k까지의 vertex만을 사용할 수 있는 path들 중

가장 짧은 path를 나타낸다

 

이제부터 계속 intermediate vertex라는 말이 나올텐데

이게 무엇이냐하면

source와 destination을 제외하고 그 중간에 들어가는

vertices들을 intermediate vertex라고 한다

즉, i에서 j로 가는 path의 intermediate vertex라고 하면

i와 j를 제외한 path의 vertices를 말한다

 

 

dp로 문제를 풀어야하니 우선 case를 구분해보자

 

case 1의 경우이다

만약 vertex k가 intermediate vertex에 들어가지 않는 경우이다

그럼 위의 변수 d에서의 intermediate vertex는

1부터 k-1까지의 vertecies가 될 것이고

이렇게 되면

 

이 등식이 성립하게 된다

 

 

이제 case 2를 보자

 

case2는 shortest path가 k를 지나가는 경우이다

이런 경우에는 shortest path를 2개로 decompose 할 수가 있다

k를 기준으로

i에서 k까지 가는 subpath p1과

k에서 j까지 가는 subpath p2로 구분할 수 있다

 

그 다음 우리가 이전시간까지 계속 나왔던 lemma에 따라서

위 2개의 subpath가는 모두 shortest path여야한다

 

그렇게 되면 p1의 intermediate vertices는 1에서 k-1 사이에 존재한다

p2에서도 동일하게 1에서 k-1 사이에 intermediate vertices가 존재하게 된다

그래서

위와 같은 식이 성립하게 된다

 

 

결국 변수 d의 상황은 이 case 1과 case 2의 상황밖에 없게 된다

 

따라서 case 1과 case 2 중에서

더 작은 값이 d의 값이 되는 것이다

 

이제 Base Case를 구해보자

 

k = 0일 때의 값을 구해보자

k가 0이라는 소리는 shortest path에 어떤 vertex도

존재하지 않는다는 뜻이다

 

이런 경우는 그냥 i와 j가 directed하게 연결되어있는 경우 뿐이다

 

따라서 k=0이면 그 값은 i에서 j로 가는 edge의 weight값과 동일해져서

아래의 식이 성립하게된다

 

이제 recursive case를 정의해보자

 

변수 d는 위와 같이

k=0일 때는 edge의 weight값

그리고 1보다 크거나 같을 때는 case1과 case2의

최솟값으로 정의해준다

 

그럼 아래와 같은 식이 성립하게 된다

 

 

또한, intermediate vertices가 1에서부터 최대 n까지밖에 없기때문에

위와 같은 식이 성립된다

 

그러고 이걸 대문자 D를 이용해서 matrix로 나타낸다

 

 

bottom up으로 shortest weight를 구하는 pseudo code이다

 

D(0)은 W의 matrix로 초기화해준다

k를 1부터 n까지 증가시키면서

D(k)는 n x n matrix로 초기화시켜준다

 

그런다음 모든 가능한 source와 모든 가능한 destination에 대해서

for loops를 돌리며 계산해주면 된다

 

1부터 n까지의 loops를 3번씩 돌리므로

time complexity는 O(N세제곱)이 된다

 

지금까지 구해준 것은 shortest path의 거리이다

그런데 거리 말고 실제 path 자체를 구하고 싶다면?

실제로 어떤 verteces를 지나서 shortest path가 되는지

구하고 싶다면 어떻게 하면 될까?

 

path 자체를 구하고 싶다면 precedessor를 저장하면서 진행해야한다

 

만약 k가 0일 때 precedessor의 값을 살펴보자

k가 0이라는 뜻은 i에서 j까지 directed 연결된 edge밖에 없다는 뜻이므로

i와 j가 같으면 weight는 무한대고 precedessor 값은 nil이 된다

i와 j가 같지 않고 실제로 edge가 존재한다면(weight가 무한대보다 작다면)

precedessor는 i가 된다

 

 

 k가 1보다 클 때의 경우를 보자

이 때도 case를 2개로 나눌 수 있다

 

case 1은 이전과 동일하게 k를 Intermediate vertex로 갖지 않는 경우이다

그럼 당연하게 k를 갖지 않게 되니 k-1과 값이 같아져서

이 식이 성립하게 될 것이다

 

case 2는 중간에 k를 반드시 지나는 경우이다

그럼 이것도 이전과 동일하게 k를 기준으로

i -> k, k -> j 2개의 subpath로 나눈다

 

lemma에 의해서 2개의 subpath 모두 shortest path가 되므로

위 식이 성립하게된다

 

위 식은 앞에서 나왔던 case1과 case2의 shortest path였다

만약 case2가 case1보다 크거나 같다면

k를 Intermediate로 갖지 않는 case1이 유효한 것이므로

case1에서의 precedessor를 저장한다

그렇지 않다면 case2의 precedessor를 저장한다

 

따라서 아래의 식이 나오게 된다

 

 

precedessor까지 함께 구하는 pseudo code를 살펴보자

 

1에서 6까지의 for문이 초기화 과정이고

7부터 12까지의 for문이 update 과정이다

 

처음에 3번째 줄에서

d[i, j]를 w[i, j]로 초기화한다

그 다음에 precedessor는 nil로 초기화한다

그런 다음 i에서 j가 서로 다르고 edge가 존재한다면

π[i, j]는 i로 초기화해준다

 

7번 부터는 실제로 알고리즘을 사용해서 update를 하는 과정이다

10번째 줄의 if문 조건을 만족하면

k를 경유하는 case2의 경우가 shortest path가 되므로

그걸로 d[i, j]와 π[i, j]를 업데이트해준다

 

 

그럼 실제 그래프를 바탕으로 matrix들을 작성해보자

 

위 오각형이 그래프이고

그래프의 각 vertex는 1부터 5까지 numbering이 되어있다

 

W는 각각 edge들의 weight들의 matrix이다

그리고 d는 d(0)일 때의 matrix인데

사실상 이건 W와 같기 때문에 동일하게 초기화해준다

마지막이 precedessor의 matrix인데

자기 자신에서 자기 자신으로 가는 경우는 nil

edge가 없는 부분은 nil로 초기화해주고

edge가 있는 경우는 source vertex로 초기화해준다

 

 

이제 k=1,i=1, j=1일 때를 계산해보자

intermediate vertex는 1이어야하는데

source도 1, dest도 1이다

 

우선 d(0)의 값이었던 d 행렬을 update 해줘야한다

d[1, 1]의 값을 계산해주기위해

이 값을 계산해보자

 

k도 1, i도 1, j도 1이므로

d[i, k] + d[k, j]의 식이

d[1, 1] + d[1, 1]이 되고

그 뒤의 식도 d[i, j]이므로 d[1, 1]이 된다

 

d[1, 1]은 0이므로

0 + 0 < 0 은 성립하지 않으므로

기존 d[1, 1]값에서 업데이트를 해주면 안된다

 

따라서 d는 변하는게 없게 되고

π도 아무것도 update 시켜주지 않는다

 

 

이제 k=1, i=4, j=2일 때를 보자

 

이 식이 성립하는지부터 살펴보자

2 + 3 < 무한대

가 되므로 위의 식은 성립한다

 

따라서 d[4, 2]는 업데이트가 2+3=5로 업데이트가 되어야한다

그래서 왼쪽에서 오른쪽의 Matrix로 업데이트를 시켜줬다

 

이제 그러면 위 식이 성립하므로

π도 update를 해줘야한다

π[i, j]는 π[k, j]와 동일하므로 위 matrix에서

π[k, j]의 값을 찾는다

π[1, 2]의 값은 1이므로 π[4, 2]도 1로 update해준다

 

 

동일하게 1개만 더 해보자..

k=2, i=1, j=4일 때를 계산해보자

 

위 식은

3 + 1 < 무한대

이므로 성립한다

 

따라서 d[1, 4]를 3 + 1 = 4로 update해준다

위와 같이 d matrix가 update가 되었다

 

이제 π도 update를 해주어야하므로

π[i, j] = π[k, j]이므로

π[1, 4] = π[2, 4]인데 π[2, 4]는 2이므로

π[1, 4]도 2로 update를 해준다

 

모든 path를 출력하는 pseudo code를 살펴보자

 

만약 i == j라면 i를 출력해준다

그리고 만약 πij가 nil이라면

i에서 j까지 가는 edge는 없는것이므로 해당 메시지를 출력해준다

 

그 나머지의 경우 (i와 j가 다르고 edge가 있을 때)

재귀적으로 PRINT-ALL-PAIRS-SHORTEST-PATH 호출한다

그러고 가장 최근에 stack에 쌓인 호출부터 처리해야하므로

recursive한 호출 뒤에 j를 print해준다

 

이제 방금 우리가 exercise했던 그래프에서

해당 코드가 어떻게 작동하는지 살펴보자

 

결국 최종 모든 vertex에 대해 다 돌린 π matrix가

위와 같이 나왔다

그리고 우리가 알고싶은건 vertex1에서 vertex2로 갈 때의

가장 짧은 path이다

 

가장 처음

PRINT-ALL-PAIRS-SHORTEST-PATH(π, 1, 2)함수를 수행한다

그럼 1과 2는 else문에 걸리게되고

재귀적으로 같은 함수에 대해서 π, 1, π[1, 2]의 값을 넣어줘야하므로

PRINT-ALL-PAIRS-SHORTEST-PATH(π, 1, 3)이 수행된다

그럼 똑같이 재귀문에 걸리게되고

π[1, 3]값인 4가 3 대신 input으로 들어가게 되어서

PRINT-ALL-PAIRS-SHORTEST-PATH(π, 1, 4)가 수행된다

또 재귀적으로 호출돼서

PRINT-ALL-PAIRS-SHORTEST-PATH(π, 1, 5)가 수행되고

다시 재귀적으로

PRINT-ALL-PAIRS-SHORTEST-PATH(π, 1, 1)이 수행되게된다

그럼 이제 i=j의 조건문에 걸리게 되므로

우선 j를 출력하게되니 1이 먼저 출력된다

 

그다음 PRINT-ALL-PAIRS-SHORTEST-PATH(π, 1, 1) 함수를 빠져나가

PRINT-ALL-PAIRS-SHORTEST-PATH(π, 1, 5) 함수의 print문을 출력해서 5가 출력되고

다시 PRINT-ALL-PAIRS-SHORTEST-PATH(π, 1, 4) 함수의 print문인 4가

다시 PRINT-ALL-PAIRS-SHORTEST-PATH(π, 1, 3) 함수의 print문인 3이

PRINT-ALL-PAIRS-SHORTEST-PATH(π, 1, 2) 함수의 print문인 2가 출력되고

모든 함수가 종료되게된다

 

따라서 순서대로 1 5 4 3 2가 출력되는 것이고

이게 i=1, j=2까지 가는 shortest path의 vertices이다

 

 

Johnson's Algorithm

마지막으로 Johnson's Algorithm을 간단하게..

살펴보고 이번 학기의 모든 강의 내용을 마치려고한다

 

 

Johnson Algorithm의 Motivation은 다음과 같다

 

사실상 우리가 위에서 봤던 Floyd-Warshall 알고리즘은

time complexity는 무조건 edge의 세제곱 만큼이다

 

하지만 다익스트라 알고리즘을 이용해서

모든 vertex에 대해 다익스트라를 돌리면

원래라면 시간복잡도가

이정도로 나오지만

만약 Edge의 개수가 O(V)라고 한다면

시간 복잡도가

이정도로 가능해진다

 

따라서 edge의 개수가 적을 경우에는

다익스트라로 모든 Vertex에 대해 수행하는게

Floyd-Warshall 보다 시간이 덜 걸리게 되는 것이다

 

하지만 다익스트라 알고리즘에는 치명적인 문제가 있었다

바로 negative weight edge가 있으면 안된다는 점이었다

 

따라서 그러면 다익스트라를 수행하기 위해서

negative weight edge를 non-negative weight로 바꿀 수 있을까?

이 질문에 의해서 Johnson's Algorithm이 개발되었다

 

그래프 edge들의 고도는 바꾸지 않고 weight만 바꾸어서

non-negative-weight를 만들어서

다익스트라로 수행해서 시간복잡도를 줄이는 것이

Johnson's Algorithm의 목표이다

 

이렇게 negative weight edge를

non negative weight edge로 변경하는 것을

reweighting이라고 한다

 

따라서 각 edge w(u, v)에 대해

reweighting해준 새로운 edge는

w에 hat을 붙여준

 

이렇게 표기하고 non-negative이다

 

또한, edge의 weight가 new weight로 바뀌어도

shortest path는 그대로 유지되어야한다

 

 

reweighting을 하기 위해서 h(u)라는 새로운 함수를 도입했다

vertex u와 associate가 되어있는 어떤 함수이다

 

새로운 weight값은

위처럼 계산해준다

 

위 식이 어떻게 나왔는지에 대한 증명인데

path p = <v0, ..., vk>에 대해서 위 식을 계산해주면

결국 중간의 값들은 다 날라가고 

가장 앞의 h(v0)과 가장 마지막의 h(vk)만 남게된다고 한다

 

따라서 

결국 w햇(p)는 위 식과 결과가 같아져서

new weight의 계산식이 나온다고 한다

 

(사실 왜 갑자기 저 증명이 나왔는지는 못들었다,,ㅎ)

 

이제 h(v) 함수를 define해보자

 

새로운 node s를 만들어준다음

node s는 다른 모든 vertex들과 이어지는

edge를 추가해준다

그런 다음 새로 추가한 edge들의 weight는

모두 0으로 셋팅한다

 

h(v)란 s에서 각각의 vertex로 가는

shortest path의 weight의 값이다

이전 시간에 증명을 한 내용인데

델타 (s, v)는 델타(s, u) + w(u, v)보다 작거나 같다

그런데 델타(s, u)는 h(u)와 동일하므로

결국 h(u) + w(u, v)가 된다

 

따라서 h(v) <= h(u) + w(u, v)라는 식이 나오고

w(u, v) + h(u) - h(v) >= 0이 되는데

위는 new weight인 w햇(u, v)의 값과 같으므로

새로운 weight는 0보다 크거나 같다는 것이 증명된다

 

그럼 위 그래프를 보며 실제로 reweighting을 한 번 해보자

 

1->2로 가는 부분은 원래 weight가 3이다

원래 weight 3에서 h(1) - h(2)를 더해주면

0 - (-1) 이므로 1이 되고 3에서 1을 더하면 4가 된다

 

따라서 vertex 1 -> vertex 2의 new weight는 4가 되는 것이다

이런 방식으로 각각의 edge의 weight에 대해서

모두 적용시켜주면된다

 

 

지금까지 본 내용을 한 번 다시 요약해보자

 

그래프 G가 주어졌을 때, 다익스트라를 돌리고 싶어서

negative weight들을 non-negative하도록 reweight를 해주는 것이다

 

그렇다면 h(v)의 값을 구하기 위해서

또 s로부터 vertex v에 대한 최단경로를 찾아야하는데

이는 Bellman-Ford를 이용해서 구해줘야한다

negative weight가 있으므로 다익스트라로 구할 수 없다

 

그래서 그렇게 새로운 new weight를 모든 edge마다

구해서 update해준다

 

그렇게 새로 바뀐 weight를 이용해서

각각의 vertex를 모두 source로 돌려가며

다익스트라를 수행하면된다

 

 

Johnson's Algorithm의 수행과정을 시각화한 것이라고 한다

 

Johnson's Algorithm의 pseudo code이다

 

source s에 대해서 각 vertex마다 벨만포드를 해주는게

시간복잡도가 O(VE)만큼 걸린다

 

그 다음에는

이 만큼 걸리는데

만약 그래프가 sparse하다면

이정도로 퉁칠 수 있다고한다

 

.

.

.

 

사실 수업에서 질문이 나왔는데

어렵게 생각하지않고 그냥 음수 weight를 다 없애려면 어떻게 해야할까 생각했을때

단순하게 가장 작은 weight를 찾아서 모든 weight에 대해

그만큼 더해주면 음수 weight가 사라지는게 아니냐는 질문이 나왔다

왜 Johnson's Algorithm처럼 저렇게 복잡하게 음수 weight를 없애야하냐는 거였다

 

그런데 이게 사실 나도 수업을 들으면서

정말 똑같은 생각을 100번 정도 ㅋㅋ 생각했었다..

 

이거 그냥 최솟값이 0이 되도록 다 더해주면 안되나?

왜 이렇게 복잡하게하지?

하는..

 

하지만 늘 이런 생각이 들 때마다

분명 우리의 옛 선인들도 다 똑같은 고민했을텐데

실험해보다가 뭔가가 안돼서 어쩔수없이 이렇게 어려운 방법을

찾아갔을 것임을 알기 때문에 그냥 그렇구나..했다

 

아무튼 질문에 대한 대답은 이게 뭐 아까 위에 설명에 보면

graph의 shortest path에 절대 영향을 주지 않아야하고

그래프의 고도?는 반드시 같아야한다는 전제 조건이 있었는데

저런 방식으로 단순하게 가장 작은 weight값을 다 더해주는 식으로 하면

그래프의 고도가 바뀔 수 있는 경우가 있다고 한다

(사실 내 머릿 속에는 똑같은 값을 모든 edge에 다 더해주는데

어떻게 하면 weight들의 고도가 바뀌는지 전혀 이해가 안된다)

 

아무튼 그래서 안된다고 한다..

나중에 gpt한테 물어보든지해서 알아보면 좋을 것 같다

 

.

.

.

 

아무튼 이렇게 해서 이번학기의 programming 수업은 여기서 끝-!

강의 내용은 끝이지만 나에겐 기말고사가 남아있다

 

기말고사는 개념 질문과 코딩테스트로 이루어져있는데

알고리즘 내용을 코딩테스트 형식의 기말고사로..?

ㅎㅎㅎ ..ㅎㅎ

참여에 의의를 둬야겠다 ㅋㅋ

 

아무튼 이번학기도 고생했고

이번 강의는 여기서 마무리-!