๐ ํ๋ก์ด๋-์จ์ ์๊ณ ๋ฆฌ๋ฌ
๐ซ ํ๋ก์ด๋-์จ์ ์๊ณ ๋ฆฌ๋ฌ - Floyd-Warshall Algorithm
์์ ์ด ๋จผ์ ๋ง๋ค์์ง๋ง, ์ด๋ฅผ ๊ฐ์ ํ ํ๋ก์ด๋๊ฐ ๋ ๋ค์๋์ฌ์.
- ๋ฌธ์ ์ ์ดํด: ๋ชจ๋ ์ ์ต๋จ๊ฒฝ๋ก ์๊ณ ๋ฆฌ๋ฌ
- ๋ชจ๋ ์ง์ ๋ค ๊ฐ์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ์๋ ค์ค
- ์ ํ
- ๋จ์ผ ์์์ ์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ๋ฌ์ ์ฌ๋ฌ ๋ฒ ๋ฐ๋ณต
- i.e. ๋ฒจ๋จผ-ํฌ๋ ์๊ณ ๋ฆฌ๋ฌ์ n๋ฒ ๋ฐ๋ณต: ฦ(n^2 e), ๊ณ ๋ฐ๋ ๊ทธ๋ํ์ ๊ฒฝ์ฐ ์ต๋ ฦ(n^4)
- ํ๋ก์ด๋-์์
์๊ณ ๋ฆฌ๋ฌ(Floyd-Warshall algorithm)
- ์์ ๊ฐ์ค์น ๊ฐ์ ์ ํ์ฉํ๋ ๋ฐฉํฅ ๊ทธ๋ํ์์ ๋ชจ๋ ์ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ฦ(n^3)์ ์ฐพ์
- ์์ ์ฌ์ดํด์ ํ์ฉ๋์ง ์์
- ๊ธฐ๋ณธ ์์ด๋์ด
- ์ ์ V={1, 2, โฆ, n}๊ณผ ๊ฐ์ E๊ฐ ์ฃผ์ด์ก์ ๋ A์ B ๋ ์ ์ ๊ฐ ์ต๋จ ๊ฒฝ๋ก ๊ธธ์ด
- = ์ ์ {1, 2, โฆ, n}์ ์ํ ์ ์ ๋ค์ ๊ฐ์ง๊ณ ๋ง๋ค ์ ์๋ ์ต๋จ ๊ฒฝ๋ก ๊ธธ์ด
- โค ์ ์ {1, 2, โฆ, n-1}์ ์ํ ์ ์ ๋ค์ ๊ฐ์ง๊ณ ๋ง๋ค ์ ์๋ ์ต๋จ ๊ฒฝ๋ก ๊ธธ์ด (์ต๋จ ๊ฒฝ๋ก๊ฐ n์ ๊ฑฐ์น๋ฉด ๊ฐ๊ณ , Like ๋ฐฐ๋ญ๋ฌธ์ )
- โฆ
- โค ์ ์ {1, 2, โฆ, k}์ ์ํ ์ ์ ๋ค์ ๊ฐ์ง๊ณ ๋ง๋ค ์ ์๋ ์ต๋จ ๊ฒฝ๋ก ๊ธธ์ด
- โฆ
- โค ์ ์ {1}์ ์ํ ์ ์ ๋ค์ ๊ฐ์ง๊ณ ๋ง๋ค ์ ์๋ ์ต๋จ ๊ฒฝ๋ก ๊ธธ์ด
- โค ์ ์ { }์ ์ํ ์ ์ ๋ค์ ๊ฐ์ง๊ณ ๋ง๋ค ์ ์๋ ์ต๋จ ๊ฒฝ๋ก ๊ธธ์ด(์๋ฌด ์ ์ ๋ ๊ฑฐ์น์ง ์์)
- ์ฃผ์ด์ง ๋ฌธ์ ์ ํฌ๊ธฐ๊ฐ ๊ฐ์ฅ ํฌ๊ณ ์ ์ ๋ฌธ์ ์ ํฌ๊ธฐ๊ฐ ์์์ ธ์ ๊ฐ์ฅ ๋ง์ง๋ง์ ์๋ ๋ฌธ์ ์ ํฌ๊ธฐ๊ฐ ๊ฐ์ฅ ์์ ๐กบ ๊ฐ์ฅ ์์ ๋ฌธ์ ์ ์ต์ ํด๋ก๋ถํฐ ์ ์ ํฐ ๋ฌธ์ ์ ์ต์ ํด๋ฅผ ๊ตฌํ ์ ์๋ค๋ฉด!!
- ๋จ์ผ ์์์ ์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ๋ฌ์ ์ฌ๋ฌ ๋ฒ ๋ฐ๋ณต
๋ชจ๋ ์ ์ต๋จ ๊ฒฝ๋ก๋, ํ๋ก์ด๋-์์
์๊ณ ๋ฆฌ๋ฌ์ ๋ชฐ๋ผ๋, ๋จ์ผ ์์์ ์ต๋จ ๊ฒฝ๋ก ์๊ณ ๋ฆฌ๋ฌ์ ์์์ ์ ๋ค๋ฅด๊ฒ n๋ฒ ๋ฐ๋ณต ์์ผ ํ ์๋ ์๋ค. (n^4)
๊ทธ๋ฐ๋ฐ ํ๋ก์ด๋-์์
์๊ณ ๋ฆฌ๋ฌ์ ์ฐ๋ฉด n^3์ผ๋ก ํ ์ ์๋ค.
์๊ณ ๋ฆฌ๋ฌ.. ๋ง์ด ์์์ผ๊ฒ ์ง?
- ๋ฌธ์ ์ ์ํ์ ์ ์
- ์ต์ข ๋ชฉํ: ๋ชจ๋ ์ ์ ๋ค ๊ฐ์ ์ต๋จ ๊ฒฝ๋ก
- ์ต์ฐ์ ๋ชฉํ: ๋ชจ๋ ์ ์ ๋ค ๊ฐ์ ์ต๋จ ๊ฒฝ๋ก ๊ธธ์ด
- ์ ์ i์์ ์ ์ j๊น์ง(iโผ>j) ์ต๋จ ๊ฒฝ๋ก ๊ธธ์ด
- = ์ ์ {1, 2, โฆ, n}์ ์ํ ์ ์ ๋ค๋ง ๊ฑฐ์น๋ iโผ>j์ ์ต๋จ ๊ฒฝ๋ก ๊ธธ์ด Dn(i, j)
- = ๋ค์ ๋ ์ต๋จ ๊ฒฝ๋ก ์ค ๋ ์งง์ ๊ฒฝ๋ก
- ์ ์ n์ ์๊ฑฐ์น๋/์์ฐ๋ ์ต๋จ ๊ฒฝ๋ก
- ์ ์ {1, 2, โฆ, n-1}์ ์ํ ์ ์ ๋ค๋ง ๊ฑฐ์น๋ ์ต๋จ ๊ฒฝ๋ก
- โ Dn-1(i, j)
- ์ ์ n์ ๊ฑฐ์น๋/์ฐ๋ ์ต๋จ ๊ฒฝ๋ก
- ์ ์ i์์ ์ ์ n์ ๊ฑฐ์ณ ์ ์ j์ ๋๋ฌํ๋ ์ต๋จ ๊ฒฝ๋ก, i ~> n ~> j
- iโผ>n๋ ์ต๋จ ๊ฒฝ๋ก๋ก ์ด๋ํ๊ณ nโผ>j๋ ์ต๋จ ๊ฒฝ๋ก๋ก ์ด๋ํด์ผ ํ๋ฏ๋ก Dn(i, n) + Dn(n, j)
- ์ด๋, iโผ>n์ ์ต๋จ ๊ฒฝ๋ก๋ ์ค๊ฐ์ ์ ์ n์ ๊ฑฐ์น์ง ์์ (์ ์ ์ : n-1)
- ์ด๋, nโผ>j์ ์ต๋จ ๊ฒฝ๋ก๋ ์ค๊ฐ์ ์ ์ n์ ๊ฑฐ์น์ง ์์ (์ ์ ์ : n-1)
- โ Dn(i, n) + Dn(n, j) = Dn-1(i, n) + Dn-1(n, j)
- ์ผ๋ฐํ
- ์ ์ {1, 2, โฆ, k}์ ์ํ ์ ์ ๋ง ๊ฑฐ์น๋ iโผ>j์ ์ต๋จ ๊ฒฝ๋ก ๊ธธ์ด Dk(i, j)
- = ๋ค์ ๋ ์ต๋จ ๊ฒฝ๋ก ์ค ๋ ์งง์ ๊ฒฝ๋ก
- ์ ์ k๋ฅผ ์๊ฑฐ์น๋/์์ฐ๋ ์ต๋จ ๊ฒฝ๋ก
- ์ ์ {1, 2, โฆ, k-1}์ ์ํ ์ ์ ๋ค๋ง ๊ฑฐ์น๋ ์ต๋จ ๊ฒฝ๋ก
- โ Dk-1(i, j)
- ์ ์ k๋ฅผ ๊ฑฐ์น๋/์ฐ๋ ์ต๋จ ๊ฒฝ๋ก
- i -{(1, 2, โฆ, k-1)์ ์ํ ์ ์ }โ k -{(1, 2, โฆ, k-1)์ ์ํ ์ ์ }โ j
- iโผ>kโผ>j์ ์ต๋จ ๊ฒฝ๋ก
- iโผ>k์ kโผ>j๋ ์ต๋จ ๊ฒฝ๋ก๋ก ์ด๋ํด์ผ ํจ: Dk(i, k) + Dk(k, j)
- ์ด๋, iโผ>k์ ์ต๋จ ๊ฒฝ๋ก๋ ์ค๊ฐ์ ์ ์ k๋ฅผ ๊ฑฐ์น์ง ์์ (์ ์ ์ : k-1)
- ์ด๋, kโผ>j์ ์ต๋จ ๊ฒฝ๋ก๋ ์ค๊ฐ์ ์ ์ k๋ฅผ ๊ฑฐ์น์ง ์์ (์ ์ ์ : k-1)
- ๐กบ Dk(i, k) + Dk(k, j) = Dk-1(i, k) + Dk-1(k, j)
Dn(i, j)๋ D(n, i, j)๋ก ์จ๋ ๋๊ธดํ๋๋ฐ, ์ด๋ ๊ฒ ๋๋ฉด 3์ฐจ์ ๋ฐฐ์ด์ ์จ์ผํ๊ณ , 3์ฐจ์ ๋ฐฐ์ด์ ๋ค๋ฃจ๊ธฐ ๋ณต์กํ๋๊น
์๋์ ์ผ๋ก ๋ค๋ฃจ๊ธฐ ์ฌ์ด 2์ฐจ์ ๋ฐฐ์ด์ ์ฌ๋ฌ ๊ฐ ๋ง๋ค์ด ์ฐ๋ ์์ผ๋ก ์ฐ๊ธฐ ์ํด n์ ์๋์ฒจ์๋ก ์ด๋ค.
Like ๋ฐฐ๋ญ ๋ฌธ์
Dn(i, j) = Min { Dn-1(i, j), Dn-1(i, n) + Dn-1(n, j) }
Dn(i, j) =
if (k > 0)
Min { Dn-1(i, j), Dn-1(i, n) + Dn-1(n, j) }
if (k == 0)
(i, j)์ ๊ฐ์ค์น
์ผ๋ฐํ์ํค๋ฉด
Dk(i, j) = Min { Dk-1(i, j), Dk-1(i, k) + Dk-1(k, j) }
๋์ ๊ณํ๋ฒ์ผ๋ก ๋ง๋ ๋ค = ๋ฐฐ์ด๋ก ๋ง๋ ๋ค
- ๋์ ๊ณํ๋ฒ
- ์ต์ฐ์ ๋ชฉํ: ์ ์ {1, โฆ, n}์ ์ํ ์ ์ ๋ง ๊ฑฐ์น๋ iโผ>j์ ์ต๋จ ๊ฒฝ๋ก ๊ธธ์ด Dn(i, j)
- 2์ฐจ์ ๋ฐฐ์ด์ ์์ Dk[i][j]์ Dk(i, j)์ ๊ฐ์ ์ ์ฅํ๊ณ ํ์ํ ๋๋ง๋ค ์ฌ์ฌ์ฉ
- ์ฃผ์ด์ง ๊ทธ๋ํ๋ ๋น์ฉ ์ธ์ ํ๋ ฌ W์ ์ ์ฅ
- ์ค๊ฐ์ ์๋ฌด ์ ์ ๋ ๊ฑฐ์น์ง ์๋ ์ต๋จ ๊ฒฝ๋ก ๊ธธ์ด๋ฅผ ์ ์ฅํ๊ธฐ ์ํ ๋ฐฐ์ด D0์์๋ถํฐ ์์ํ์ฌ ์ฐจ๋ก๋ก ๋ฐฐ์ด D1, D2, โฆ, Dn์ ์์ฑํ๋ ๋จ๊ณ๋ฅผ ๊ฑฐ์นจ(๋ฐฐ์ด D0์ ์ธ์ ํ๋ ฌ W ์ ๋์ผ)
- ๋ฐฐ์ด Dk์๋ ์ต๋จ ๊ฒฝ๋ก ๊ธธ์ด๋ง ์ ์ฅ ๐กบ ์ต์ข
๋ชฉํ์ธ ์ต๋จ ๊ฒฝ๋ก๋ฅผ ๊ธฐ์ตํ ๋ฐฐ์ด์ด ํ์
- Dk[i][j]๊ฐ ๋ณ๊ฒฝ๋๋ฉด k๋ฅผ ๋ฐฐ์ด Vk[i][j]์ ์ ์ฅ. ์ฆ iโผ>j์ ์ต๋จ ๊ฒฝ๋ก๊ฐ k๋ฅผ ๊ฒฝ์ ํ๋ค๋ฉด Vk[i][j]= k๋ก ์ง์
- Vn[i][j]๋ถํฐ ๊ฑฐ๊พธ๋ก ์กฐ์ฌํด ๋ด๋ ค๊ฐ๋ฉด iโผ>j์ ์ต๋จ ๊ฒฝ๋ก๊ฐ ์ด๋ค ์ ์ ๋ค์ ๊ฒฝ์ ํ๋์ง ์ ์ ์์
Dk[i][j] =
if (k > 0)
Min { Dk-1[i][j], Dk-1[i][k] + Dk-1[i][k] }
if (k == 0)
[i][j]์ ๊ฐ์ค์น
- ์๊ณ ๋ฆฌ์ฆ
- ์ฌ๋ฌ ๊ฐ์ ๋ฐฐ์ด์ ์ฌ์ฉํ์ง ์๊ณ ํ๋์ ๋ฐฐ์ด๋ง ์ฌ์ฉํด์ ๊ณ์ ๋ฎ์ด์ฐ๊ธฐ๋ฅผ ๋ฐ๋ณต
- ์์์ Dk[i][j]๋ฅผ ๊ตฌํ๊ธฐ ์ํด ์ฌ์ฉ๋๋ Dk-1[i][k]๋ Dk[i][k]์ ๊ฐ๊ณ Dk-1[k][j]๋ Dk[k][j]์ ๊ฐ์ผ๋ฏ๋ก ์ด ๋ ๊ฐ์ Dk๋ฅผ ๊ตฌํ๋ k ๋ฒ์งธ ๋ฐ๋ณต๋ฌธ ๋ด์์๋ ์ ๋๋ก ๋ณ๊ฒฝ๋์ง ์๊ธฐ ๋๋ฌธ
- Dk์ ๊ตฌํ๊ธฐ ์ํด ์ฐธ๊ณ ํ๋ ๊ฐ์ Dk-1[k][?] ๋ Dk-1[?][k], Dk-1์ kํ๊ณผ k์ด์ ์์๋ค ๋ฟ
- ๋ณต์ก๋: ฦ(n3)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void FloydWarshallDP(int d[][MAX], int n)
{
int V[MAX][MAX] = {0};
for (int k = 1; k <= n; k++) // ๊ฐ ์ ์ ์ ๋ํด : n
for (int i = 1; i <= n; i++) // ํ : n
for (int j = 1; j <= n; j++) // ์ด : n
if (D[i][k] + D[k][j] < D[i][j]) // k๋ฅผ ๊ฒฝ์ ํ๋ ๊ฑฐ๋ฆฌ๊ฐ ๋ ์งง์ผ๋ฉด
{
D[i][j] = D[i][k] + D[k][j]; // ๊ฑฐ๋ฆฌ
V[i][j] = k; // ๊ฒฝ์
}
// ๋ณต์ก๋ : n * n * n
}
๐ซ ์ดํ์ ํ์ ๋ฌธ์
(์ถ์ด์ ํํฌ)(transitive closure)
๐ซง ์ดํ์ ๊ด๊ณ
R์ด ์งํฉ S์ ๋ํ ๊ด๊ณ๋ผ ํ ๋ ๋ชจ๋ a,b,c โ S์ ๋ํด (a,b)โR์ด๊ณ (b,c)โR์ด๋ฉด (a,c)โR์ ๋ง์กฑํ๋ ๊ฒฝ์ฐ R์ ์ดํ์ ๋๋ ์ดํ์ ๊ด๊ณ๋ผ๊ณ ํ๋ค.
๐ซง ์ดํ์ ํ์
R์ด ์งํฉ S์ ๋ํ ๊ด๊ณ๋ผ ํ ๋ ๊ด๊ณ R์ ํฌํจํ๋ ๊ฐ์ฅ ์์ ์ดํ์ ์ธ ๊ด๊ณ๋ฅผ R์ ์ดํ์ ํ์๋ผ๊ณ ํ๋ค.
๐ซง _
- ๋ฌธ์ : ๊ทธ๋ํ์ ๊ฐ ์ ์ ์ฌ์ด์ ๊ฒฝ๋ก๊ฐ ์กด์ฌํ๋๊ฐ?
- ์ดํ์ ํ์ ๊ด๊ณ R์ ๋ฐฉํฅ ๊ทธ๋ํ๋ก ๋ํ๋ธ๋ค๋ฉด
- a์์ b๋ก ๊ฒฝ๋ก๊ฐ ์กด์ฌํ๊ณ b์์ c๋ก ๊ฒฝ๋ก๊ฐ ์กด์ฌํ๋ฉด ๋ฐ๋์ (a, c)โR
- โด ๊ด๊ณ์์์ ์ดํ์ ํ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ โก ๊ทธ๋ํ์ ์ ์ ์ฌ์ด์ ๊ฒฝ๋ก๊ฐ ์กด์ฌํ๋์ง ์ฌ๋ถ๋ฅผ ์กฐ์ฌํ๋ ๋ฌธ์
- ๐กบ ํ๋ก์ด๋-์์ ์ ์๊ณ ๋ฆฌ์ฆ์ ์ด์ฉํ์ฌ ํด๊ฒฐ