[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ํ๋ก์ด๋-์์ ์๊ณ ๋ฆฌ์ฆ(Floyd-Warshall Algorithm)
All Pairs Shortest Path
์ง๊ธ๊น์ง ๋ค๋ค๋ ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ด๋ ๋ฒจ๋งํฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ๋ชจ๋ ํ๋์ ์ ์ ์ผ๋ก๋ถํฐ ๋ค๋ฅธ ๋ชจ๋ ์ ์ ๊น์ง์ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ Single source Shortest Path(SSP)
๋ฌธ์ ๋ฅผ ํ๊ธฐ์ํ ์๊ณ ๋ฆฌ์ฆ์ด์๋ค. ์ค๋ ์๊ฐํ ํ๋ก์ด๋-์์
์๊ณ ๋ฆฌ์ฆ์ ๊ทธ๋ํ์ ์๋ ๋ชจ๋ ๋ชจ๋ ์ ์ ์ ๋ํด ๊ฐ ์ ์ ๋ค์ด ๋ค๋ฅธ ์ ์ ๋ค๊น์ง ๋๋ฌํ๊ธฐ ์ํด ํ์ํ ๋ชจ๋ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค.
Concept
์๊ณ ๋ฆฌ์ฆ์ ์๋ฆฌ๋ ๋จ์ํ๋ค. ์ด๋ค ์ ์ X๋ก๋ถํฐ Y๊น์ง์ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๊ธฐ ์ํด์ ์ค๊ฐ์ ๊ฑฐ์ณ๊ฐ ์ ์๋ ๋ชจ๋ ์ ์ ๋ค์ ํ์ธํด๋ณด๊ณ ๊ทธ ์ค ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๋ง๋๋ ๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ๊ฒ์ด๋ค. ๋ค์ ์์์ ๋ณด์.
์ฌ๊ธฐ์ dij(k) ์ 1๋ถํฐ k ๊น์ง์ ์ ์ ๋ค์ ๊ฑฐ์ณ๊ฐ๋ ๊ฒฝ๋ก ์ค ์ต๋จ ๊ฒฝ๋ก์ ๊ธธ์ด๋ฅผ ๋ํ๋ธ๋ค. ์ต๋จ ๊ฒฝ๋ก๋ฅผ ๊ตฌํ๊ธฐ ์ํด์๋ ๋ ๊ฐ์ง์ ๊ฒฝ์ฐ๋ฅผ ์๊ฐํด ๋ณผ ์ ์๋ค.
k = 0
dij(0) ์ ์๋ฌด๊ณณ๋ ๊ฑฐ์ณ์ค์ง ์๊ณ ์ ์ i ์์ ์ ์ j๊น์ง ๊ณง๋ฐ๋ก ์ด๋ํ ๊ฒฝ์ฐ๋ฅผ ์๋ฏธํ๋ค. ๊ทธ๋ฆฌ๊ณ ์ด๊ฒ์ ๋ค๋ฅด๊ฒ ํํํ๋ฉด, ์ ์ i์ j ์ฌ์ด์ ๊ฐ์ ๊ฑฐ๋ฆฌ๋ฅผ ์๋ฏธํ๊ธฐ ๋๋ฌธ์ ์ฐ๋ฆฌ๋ wij ๋ผ๊ณ ๋ ํํํ ์ ์์ ๊ฒ์ด๋ค.
k > 1
k ๊ฐ 0๋ณด๋ค ํฌ๋ค๋ ๊ฒ์ i ๋ถํฐ j๊น์ง ๊ฐ๋ ๊ธธ์ ๊ฒฝ์ ํ ์ ์๋ ์ ์ ์ด ์๋ค๋ ๊ฒ์ ์๋ฏธํ๋ค. ์ด ๊ฒฝ์ฐ์๋ ij์ ๊ธธ์ด์ i ์์ k ๊น์ง์ ๊ธธ์ด์ k๋ถํฐ j ๊น์ง์ ๊ธธ์ด์ ํฉ์ ๊ตฌํด์ ๋ ๊ฐ์ด ์์ ๊ฒ์ ์ต๋จ๊ฒฝ๋ก์ ๊ธธ์ด๋ก ์ ํ๋ค.
Implementation - O(N^3)
ํ๋ก์ด๋ ์์ฌ ์๊ณ ๋ฆฌ์ฆ์ 2์ฐจ์ ๋ฐฐ์ด์ ๋ง๋ค์ด์ DP๋ก ์ ๊ทผํ๋ค. ๋ฐฐ์ด์ ๊ฐ ์์๋ i ์ j ์ฌ์ด์ ๊ณ์ฐ๋ ์ต์์ ๋น์ฉ์ ์ ์ฅํ๋ค. ๊ฐ ์ ์ ์ ๋ํด์ ๋ชจ๋ ์ ์ ์ ๋ํด ๊ฑฐ์ณ๊ฐ๋ ๋น์ฉ์ ๊ณ์ฐํด์ผํ๊ธฐ ๋ผ๋ฌธ์ 3์ค์ผ๋ก ์ค์ฒฉ๋ for ๋ฌธ์ ํตํด์ ๊ณ์ฐ์ ์ํํ๋ค.
Floyd_Warshall(w, n){
for (int i = 0 ; i <= n ; i++){
for (int j = 0 ; j <= n ; j++){
if (i == j) d[i][j] = 0; // ์๊ธฐ ์์ ์ ๋ํ ๊ฑฐ๋ฆฌ๋ 0์ผ๋ก ์ด๊ธฐํ
else d[i][j] = INF; // ์ด์ธ์ ์ ์ ์ ๋ฌดํ๋๋ก ์ด๊ธฐํ
d[i][j] = w[i][j]; // ์
๋ ฅ๋ฐ์ ๊ทธ๋ํ์ ๊ฐ์ ์ ๋ณด๋ก ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ์ด๊ธฐํ
}
}
}
for (int k = 0 ; k <= n ; k++){
for (int i = 0 ; i <= n ; i++){
for (int j = 0 ; j <= n ; j++){
if (d[i][k] + d[k][j] < d[i][j]){
d[i][j] = d[i][k] + d[k][j]; // k๋ฅผ ๊ฑฐ์ณ์
pred[i][j] = k; // ๊ฒฝ๋ก ์ ๋ณด๋ฅผ ์ ์ฅ
}
}
}
}
Example
ํ๋ก์ด๋-์์ ์๊ณ ๋ฆฌ์ฆ์ด ์ด๋ป๊ฒ ์ ์ฉ๋๋์ง ์ ๊ทธ๋ํ๋ฅผ ํตํด์ ์์๋ณด์.
Phase 1 (k = 0)
๋จผ์ ๊ทธ๋ํ๋ฅผ ๊ธฐ๋ฐ์ผ๋ก ๋ ๊ฐ์ 2์ฐจ์ ๋ฐฐ์ด์ ์ด๊ธฐํ ํ๋ค. ๊ฐ ๋ฐฐ์ด ์์ [i][j]๋ i๋ถํฐ j๊น์ง์ ๊ฐ์ ์ ๋ณด๋ฅผ ์๋ฏธํ๋ค. ๋ฐฐ์ด D๋ ํ์ฌ๊น์ง ๊ณ์ฐ๋ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ ์ฅํ๊ณ , P๋ ํด๋น ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๋ง๋๋ ๋ฐ๋ก ์ด์ ์ ์ ์ ์ ์ฅํ๊ฒ ๋๋ค.
์ฐ๊ฒฐ์ด ๋ง๋ค์ด์์ง ์์ ์ ์ ๋ผ๋ฆฌ๋ ๋ฌดํ๋๋ก ํ์ํ๊ณ , ์ด์ ์ ์ ์ด ์๋ ๊ฒฝ์ฐ์๋ NIL๋ก ํ๊ธฐํ๋ค.
Phase 2 (k = 1)
์ด์ ๋ชจ๋ ์ ์ ์ ๋ํด์ ์ ์ 1์ ๊ฑฐ์ณค์ ๋์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ์ฐํด ๊ธฐ์กด ๊ฑฐ๋ฆฌ๋ณด๋ค ์งง๋ค๋ฉด ์ต๋จ๊ฑฐ๋ฆฌ์ ์ต๋จ ๊ฒฝ๋ก๋ก ์ ๋ฐ์ดํธ ํ๋ค. ํ๋ก์ด๋ ์๊ณ ๋ฆฌ์ฆ์์๋ ์ค๊ฐ์ง์ ์ ๊ฑฐ์ณ๊ฐ์ ๋์ ๊ฑฐ๋ฆฌ๋ฅผ ํ์ธํด์ ์ต๋จ๊ฒฝ๋ก๋ฅผ ๊ฐฑ์ ํ๊ธฐ ๋๋ฌธ์ ๋ชจ๋ ๋ฐฐ์ด ์์์ ๋ํด์ ๋ค์๊ณผ ๊ฐ์ ์์ ์ ๊ฑฐ์ณ์ผํ๋ค.
- ์ค๊ฐ์ง์ ์ผ๋ก ์ ํํ k๋ก i ์ j๋ฅผ ์ด์ ๊ฐ์ ์ ๋๋๋ค.
- ์ด๋ฌ๋ฉด ๊ฐ์ ik ์ kj ๊ฐ ๋ง๋ค์ด์ง๋๋ฐ, ์ด ๊ฐ์ ์ ์ด๋ฏธ ํ ์ด๋ธ์ ์ ์ฅ๋์ด ์๋ ๊ฐ์ ์ด๊ธฐ ๋๋ฌธ์ ๋ ๊ฐ์ ๋ํด ๊ฒฝ์ ํ์ ๋์ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ๋ค.(d[i][k] + d[k][j])
- ํ์ฌ ์ต๋จ๊ฑฐ๋ฆฌ์ ๊ฒฝ์ ํ์ ๋์ ๊ฐ์ ๊ฑฐ๋ฆฌ๋ฅผ ๋น๊ตํด์ ๋ ์์ ๊ฐ์ผ๋ก ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ์ ๋ฐ์ดํธ ํ๋ค.
d[4][5]๋ฅผ ๋ณด๋ฉด, k๊ฐ 0์ด์์ ๋๋ ๋ฌดํ๋ ๊ฐ์ด์ง๋ง, k๊ฐ 1์ผ ๋ 1๋ฒ ์ ์ ์ ๊ฑฐ์ณ๊ฐ๋ค๊ณ ํ๋ฉด, d[4][1]=2
์ d[1][5]=-4
๋ฅผ ๋ํด -2 ์ ๊ฑฐ๋ฆฌ๋ฅผ ์ป๊ฒ๋๊ณ ์ด ๊ฐ์ ๋ฌดํ๋ ๊ฐ๋ณด๋ค ์๊ธฐ ๋๋ฌธ์ ์๋ก์ด ์ต๋จ๊ฑฐ๋ฆฌ๋ -2๋ก ์
๋ฐ์ดํธ ๋๋ค.
๋๋ถ์ด์ ์๋ก์ด ์ต๋จ๊ฑฐ๋ฆฌ๊ฐ ์๊ฒผ๊ธฐ ๋๋ฌธ์ ๊ฒฝ๋ก์ ์ด์ ์ ์ ์ ์ ์ฅํ๋ P ๋ฐฐ์ด์ P[4][5] ๋ ๊ฒฝ์ ํ 1๋ก ๋ณ๊ฒฝ๋๋ค.
๋, d[4][2] ์ญ์ ๋ฌดํ๋ ์๋ ์ต๋จ๊ฑฐ๋ฆฌ์, 1์ ๊ฒฝ์ ํ์ ๋์ ๊ฑฐ๋ฆฌ์ธ d[4][1] + d[1][2] = 2 + 3 = 5
๊ฐ 4์์ ๋ฐ๋ก 2๋ก ๊ฐ๋ ๊ฒฝ๋ก์ธ ๋ฌดํ๋๋ณด๋ค ์๊ธฐ ๋๋ฌธ์ ์๋ก์ด ๊ฐ์ธ 5๋ก ์
๋ฐ์ดํธ ๋๊ณ ๊ฒฝ๋ก ํ
์ด๋ธ์์๋ NIL์์ 1๋ก ์
๋ฐ์ดํธ ๋๋ค.
Phase 3 (k = 2)
์ด์ ์ ์ 2๋ฒ์ ๊ฑฐ์ณ๊ฐ๋ ๋ชจ๋ ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ์ฐํ๋ค.
- d[1][4] ๋
d[1][2] + d[2][4] = 3 + 1 = 4
๊ฐ ๊ธฐ์กด ์ต๋จ๊ฑฐ๋ฆฌ์ธ ๋ฌดํ๋ ๋ณด๋ค ์๊ธฐ ๋๋ฌธ์ ์๋ก์ด ์ต๋จ๊ฑฐ๋ฆฌ๋ 4 ๋ก ์ ๋ฐ์ดํธ ๋๋ค. - d[3][4] ๋
d[3][2] + d[2][4] = 4 + 1 = 5
๊ฐ ๊ธฐ์กด ์ต๋จ ๊ฑฐ๋ฆฌ์ธ ๋ฌดํ๋ ๋ณด๋ค ์๊ธฐ ๋๋ฌธ์ ์๋ก์ด ์ต๋จ๊ฑฐ๋ฆฌ๋ 5 ๋ก ์ ๋ฐ์ดํธ ๋๋ค. - d[3][5] ๋
d[3][2] + d[2][5] = 4 + 7 = 11
์ด ๊ธฐ์กด ์ต๋จ ๊ฑฐ๋ฆฌ์ธ ๋ฌดํ๋ ๋ณด๋ค ์๊ธฐ ๋๋ฌธ์ ์๋ก์ด ์ต๋จ๊ฑฐ๋ฆฌ๋ 11 ๋ก ์ ๋ฐ์ดํธ ๋๋ค.
์ด๋ฒ ํ์ฐจ์ ์ ๋ฐ์ดํธ๋ ์๋ฆฌ๋ค์ ๋ชจ๋ ์ด์ ์ ์ ์ด 2๋ก ๊ฐฑ์ ๋๋ค. ์๋๋ฉด 2๋ฅผ ๊ฑฐ์ณ์์ผ๋๊น..!
Phase 4 (k = 3)
3๋ฒ ์ ์ ์ ๋ํด ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ์ฐํด๋ณด์.
- d[4][2] ๋
d[4][3] + d[3][2] = -5 + 4 = -1
์ด ๊ธฐ์กด ์ต๋จ ๊ฑฐ๋ฆฌ์ธ 5 ๋ณด๋ค ์๊ธฐ ๋๋ฌธ์ ์๋ก์ด ์ต๋จ๊ฑฐ๋ฆฌ๋ -1๋ก ๊ฐฑ์ ๋๋ค.
Phase 5 (k = 4)
4๋ฒ ์ ์ ์ ๊ฑฐ์ณ๊ฐ๋ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ์ฐํด๋ณด์
- d[1][3] ๋
d[1][4] + d[4][3] = 4 + -5 = -1
์ด ๊ธฐ์กด ์ต๋จ ๊ฑฐ๋ฆฌ์ธ 8๋ณด๋ค ์งง๊ธฐ ๋๋ฌธ์ ์ต๋จ๊ฑฐ๋ฆฌ๋ -1๋ก ๊ฐฑ์ ๋๋ค. - d[2][1] ์
d[2][4] + d[4][1] = 1 + 2 = 3
์ด ๊ธฐ์กด ์ต๋จ ๊ฑฐ๋ฆฌ์ธ ๋ฌดํ๋ ๋ณด๋ค ์๊ธฐ ๋๋ฌธ์ ์ต๋จ๊ฑฐ๋ฆฌ๋ 3์ด ๋๋ค. - d[2][3] ์
d[2][4] + d[4][3] = 1 + -5 = -4
๊ฐ ๊ธฐ์กด ์ต๋จ๊ฑฐ๋ฆฌ์ธ ๋ฌดํ๋ ๋ณด๋ค ์๊ธฐ ๋๋ฌธ์ ์ต๋จ๊ฑฐ๋ฆฌ๋ -4๋ก ๊ฐฑ์ ๋๋ค. - d[2][5] ์
d[2][4] + d[4][5] = 1 + -2 = -1
๊ฐ ๊ธฐ์กด ์ต๋จ ๊ฑฐ๋ฆฌ์ธ 7๋ณด๋ค ์๊ธฐ ๋๋ฌธ์ ์ต๋จ๊ฑฐ๋ฆฌ๋ -1๋ก ๊ฐฑ์ ๋๋ค. - d[3][1] ์
d[3][4] + d[4][1] = 5 + 2 = 7
์ด ๊ธฐ์กด ์ต๋จ ๊ฑฐ๋ฆฌ์ธ ๋ฌดํ๋ ๋ชจ๋ค ์๊ธฐ ๋๋ฌธ์ ์ต๋จ๊ฑฐ๋ฆฌ๋ 7๋ก ๊ฐฑ์ ๋๋ค. - d[3][5] ๋
d[3][4] + d[4][5] = 5 + -2 = 3
์ด ๊ธฐ์กด ์ต๋จ๊ฑฐ๋ฆฌ์ธ 11๋ณด๋ค ์๊ธฐ ๋๋ฌธ์ ์ต๋จ๊ฑฐ๋ฆฌ๋ 3์ผ๋ก ๊ฐฑ์ ๋๋ค. - d[5][1] ์
d[5][4] + d[4][1] = 6 + 2 = 8
์ด ๊ธฐ์กด ์ต๋จ ๊ฑฐ๋ฆฌ์ธ ๋ฌดํ๋ ๋ณด๋ค ์๊ธฐ ๋๋ฌธ์ ์ต๋จ๊ฑฐ๋ฆฌ๋ 8๋ก ๊ฐฑ์ ๋๋ค. - d[5][2] ๋
d[5][4] + d[4][2] = 6 + -1 = 5
์ด ๊ธฐ์กด ์ต๋จ๊ฑฐ๋ฆฌ์ธ ๋ฌดํ๋ ๋ณด๋ค ์๊ธฐ ๋๋ฌธ์ ์ต๋จ๊ฑฐ๋ฆฌ๋ 5๋ก ๊ฐฑ์ ๋๋ค. - d[5][3] ์
d[5][4] + d[4][3] = 6 + -5 = 1
์ด ๊ธฐ์กด ์ต๋จ๊ฑฐ๋ฆฌ์ธ ๋ฌดํ๋๋ณด๋ค ์๊ธฐ ๋๋ฌธ์ ์ต๋จ๊ฑฐ๋ฆฌ๋ 1์ด ๋๋ค.
์ด๋ฒ ๋ฐ๋ณต์์ ๊ฐฑ์ ๋ ๋ชจ๋ ์ ์ ๋ค์ ์ด์ ๊ฒฝ๋ก๊ฐ 4๋ก ๊ฐฑ์ ๋๋ค.
Phase 6 (k = 5)
๋ง์ง๋ง์ผ๋ก ์ ์ 5๋ฅผ ๊ฒฝ์ ํ๋ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ์ฐํด๋ณด์
- d[1][2] ๋
d[1][5] + d[5][2] = -4 + 5 = 1
์ด ๊ธฐ์กด ์ต๋จ๊ฒฝ๋ก์ธ 3๋ณด๋ค ์๊ธฐ ๋๋ฌธ์ ์ต๋จ๊ฑฐ๋ฆฌ๋ 1์ด ๋๋ค. - d[1][3] ์
d[1][5] + d[5][3] = -4 + 1 = -3
์ด ๊ธฐ์กด ์ต๋จ๊ฒฝ๋ก์ธ -1๋ณด๋ค ์๊ธฐ ๋๋ฌธ์ ์ต๋จ๊ฑฐ๋ฆฌ๋ -3์ด ๋๋ค. - d[1][4] ๋
d[1][5] + d[5][4] = -4 + 6 = 2
๊ฐ ๊ธฐ์กด ์ต๋จ๊ฒฝ๋ก์ธ 4๋ณด๋ค ์๊ธฐ ๋๋ฌธ์ ์ต๋จ๊ฑฐ๋ฆฌ๋ 2๊ฐ ๋๋ค.
'๐ฎ ์จ-์์ค > ๐ ์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๊ณ์์ ๋ ฌ(Counting Sort) (3) | 2021.07.18 |
---|---|
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ํต์ ๋ ฌ(Quick Sort) (1) | 2021.07.18 |
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ์์์ ๋ ฌ(Topological Sort) (0) | 2021.07.18 |
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] DAG์์ ์ต๋จ๊ฒฝ๋ก๋ฅผ ์ฐพ๋ ๋ฒ (0) | 2021.07.18 |
[์๊ณ ๋ฆฌ์ฆ ์ ๋ฆฌ] ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ(Dijkstra Algorithm) (0) | 2021.07.18 |
๋๊ธ
์ด ๊ธ ๊ณต์ ํ๊ธฐ
-
๊ตฌ๋
ํ๊ธฐ
๊ตฌ๋ ํ๊ธฐ
-
์นด์นด์คํก
์นด์นด์คํก
-
๋ผ์ธ
๋ผ์ธ
-
ํธ์ํฐ
ํธ์ํฐ
-
Facebook
Facebook
-
์นด์นด์ค์คํ ๋ฆฌ
์นด์นด์ค์คํ ๋ฆฌ
-
๋ฐด๋
๋ฐด๋
-
๋ค์ด๋ฒ ๋ธ๋ก๊ทธ
๋ค์ด๋ฒ ๋ธ๋ก๊ทธ
-
Pocket
Pocket
-
Evernote
Evernote