๊ธ€ ์ž‘์„ฑ์ž: ๊ฐœ๋ฐœํ•˜๋Š” ํ›ˆ์ด

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์„ ๊ฑฐ์ณค์„ ๋•Œ์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ„์‚ฐํ•ด ๊ธฐ์กด ๊ฑฐ๋ฆฌ๋ณด๋‹ค ์งง๋‹ค๋ฉด ์ตœ๋‹จ๊ฑฐ๋ฆฌ์™€ ์ตœ๋‹จ ๊ฒฝ๋กœ๋กœ ์—…๋ฐ์ดํŠธ ํ•œ๋‹ค. ํ”Œ๋กœ์ด๋“œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์—์„œ๋Š” ์ค‘๊ฐ„์ง€์ ์„ ๊ฑฐ์ณ๊ฐ”์„ ๋•Œ์˜ ๊ฑฐ๋ฆฌ๋ฅผ ํ™•์ธํ•ด์„œ ์ตœ๋‹จ๊ฒฝ๋กœ๋ฅผ ๊ฐฑ์‹ ํ•˜๊ธฐ ๋–„๋ฌธ์— ๋ชจ๋“  ๋ฐฐ์—ด ์š”์†Œ์— ๋Œ€ํ•ด์„œ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ž‘์—…์„ ๊ฑฐ์ณ์•ผํ•œ๋‹ค.

  1. ์ค‘๊ฐ„์ง€์ ์œผ๋กœ ์„ ํƒํ•œ k๋กœ i ์™€ j๋ฅผ ์ด์€ ๊ฐ„์„ ์„ ๋‚˜๋ˆˆ๋‹ค.
  2. ์ด๋Ÿฌ๋ฉด ๊ฐ„์„  ik ์™€ kj ๊ฐ€ ๋งŒ๋“ค์–ด์ง€๋Š”๋ฐ, ์ด ๊ฐ„์„ ์€ ์ด๋ฏธ ํ…Œ์ด๋ธ”์— ์ €์žฅ๋˜์–ด ์žˆ๋Š” ๊ฐ„์„ ์ด๊ธฐ ๋•Œ๋ฌธ์— ๋‘ ๊ฐ’์„ ๋”ํ•ด ๊ฒฝ์œ ํ–ˆ์„ ๋•Œ์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•œ๋‹ค.(d[i][k] + d[k][j])
  3. ํ˜„์žฌ ์ตœ๋‹จ๊ฑฐ๋ฆฌ์™€ ๊ฒฝ์œ ํ–ˆ์„ ๋•Œ์˜ ๊ฐ„์„ ๊ฑฐ๋ฆฌ๋ฅผ ๋น„๊ตํ•ด์„œ ๋” ์ž‘์€ ๊ฐ’์œผ๋กœ ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋ฅผ ์—…๋ฐ์ดํŠธ ํ•œ๋‹ค.

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๋ฒˆ์„ ๊ฑฐ์ณ๊ฐ€๋Š” ๋ชจ๋“  ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ„์‚ฐํ•œ๋‹ค.

  1. d[1][4] ๋Š” d[1][2] + d[2][4] = 3 + 1 = 4 ๊ฐ€ ๊ธฐ์กด ์ตœ๋‹จ๊ฑฐ๋ฆฌ์ธ ๋ฌดํ•œ๋Œ€ ๋ณด๋‹ค ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ์ƒˆ๋กœ์šด ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” 4 ๋กœ ์—…๋ฐ์ดํŠธ ๋œ๋‹ค.
  2. d[3][4] ๋Š” d[3][2] + d[2][4] = 4 + 1 = 5 ๊ฐ€ ๊ธฐ์กด ์ตœ๋‹จ ๊ฑฐ๋ฆฌ์ธ ๋ฌดํ•œ๋Œ€ ๋ณด๋‹ค ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ์ƒˆ๋กœ์šด ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” 5 ๋กœ ์—…๋ฐ์ดํŠธ ๋œ๋‹ค.
  3. d[3][5] ๋Š” d[3][2] + d[2][5] = 4 + 7 = 11 ์ด ๊ธฐ์กด ์ตœ๋‹จ ๊ฑฐ๋ฆฌ์ธ ๋ฌดํ•œ๋Œ€ ๋ณด๋‹ค ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ์ƒˆ๋กœ์šด ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” 11 ๋กœ ์—…๋ฐ์ดํŠธ ๋œ๋‹ค.

์ด๋ฒˆ ํšŒ์ฐจ์— ์—…๋ฐ์ดํŠธ๋œ ์ž๋ฆฌ๋“ค์€ ๋ชจ๋‘ ์ด์ „ ์ •์ ์ด 2๋กœ ๊ฐฑ์‹ ๋œ๋‹ค. ์™œ๋ƒ๋ฉด 2๋ฅผ ๊ฑฐ์ณ์™”์œผ๋‹ˆ๊นŒ..!

Phase 4 (k = 3)

3๋ฒˆ ์ •์ ์— ๋Œ€ํ•ด ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ„์‚ฐํ•ด๋ณด์ž.

  1. d[4][2] ๋Š” d[4][3] + d[3][2] = -5 + 4 = -1 ์ด ๊ธฐ์กด ์ตœ๋‹จ ๊ฑฐ๋ฆฌ์ธ 5 ๋ณด๋‹ค ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ์ƒˆ๋กœ์šด ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” -1๋กœ ๊ฐฑ์‹ ๋œ๋‹ค.

Phase 5 (k = 4)

4๋ฒˆ ์ •์ ์„ ๊ฑฐ์ณ๊ฐ€๋Š” ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ„์‚ฐํ•ด๋ณด์ž

  1. d[1][3] ๋Š” d[1][4] + d[4][3] = 4 + -5 = -1 ์ด ๊ธฐ์กด ์ตœ๋‹จ ๊ฑฐ๋ฆฌ์ธ 8๋ณด๋‹ค ์งง๊ธฐ ๋•Œ๋ฌธ์— ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” -1๋กœ ๊ฐฑ์‹ ๋œ๋‹ค.
  2. d[2][1] ์€ d[2][4] + d[4][1] = 1 + 2 = 3 ์ด ๊ธฐ์กด ์ตœ๋‹จ ๊ฑฐ๋ฆฌ์ธ ๋ฌดํ•œ๋Œ€ ๋ณด๋‹ค ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” 3์ด ๋œ๋‹ค.
  3. d[2][3] ์€ d[2][4] + d[4][3] = 1 + -5 = -4 ๊ฐ€ ๊ธฐ์กด ์ตœ๋‹จ๊ฑฐ๋ฆฌ์ธ ๋ฌดํ•œ๋Œ€ ๋ณด๋‹ค ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” -4๋กœ ๊ฐฑ์‹ ๋œ๋‹ค.
  4. d[2][5] ์€ d[2][4] + d[4][5] = 1 + -2 = -1 ๊ฐ€ ๊ธฐ์กด ์ตœ๋‹จ ๊ฑฐ๋ฆฌ์ธ 7๋ณด๋‹ค ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” -1๋กœ ๊ฐฑ์‹ ๋œ๋‹ค.
  5. d[3][1] ์€ d[3][4] + d[4][1] = 5 + 2 = 7 ์ด ๊ธฐ์กด ์ตœ๋‹จ ๊ฑฐ๋ฆฌ์ธ ๋ฌดํ•œ๋Œ€ ๋ชจ๋‹ค ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” 7๋กœ ๊ฐฑ์‹ ๋œ๋‹ค.
  6. d[3][5] ๋Š” d[3][4] + d[4][5] = 5 + -2 = 3 ์ด ๊ธฐ์กด ์ตœ๋‹จ๊ฑฐ๋ฆฌ์ธ 11๋ณด๋‹ค ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” 3์œผ๋กœ ๊ฐฑ์‹ ๋œ๋‹ค.
  7. d[5][1] ์€ d[5][4] + d[4][1] = 6 + 2 = 8 ์ด ๊ธฐ์กด ์ตœ๋‹จ ๊ฑฐ๋ฆฌ์ธ ๋ฌดํ•œ๋Œ€ ๋ณด๋‹ค ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” 8๋กœ ๊ฐฑ์‹ ๋œ๋‹ค.
  8. d[5][2] ๋Š” d[5][4] + d[4][2] = 6 + -1 = 5 ์ด ๊ธฐ์กด ์ตœ๋‹จ๊ฑฐ๋ฆฌ์ธ ๋ฌดํ•œ๋Œ€ ๋ณด๋‹ค ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” 5๋กœ ๊ฐฑ์‹ ๋œ๋‹ค.
  9. d[5][3] ์€ d[5][4] + d[4][3] = 6 + -5 = 1 ์ด ๊ธฐ์กด ์ตœ๋‹จ๊ฑฐ๋ฆฌ์ธ ๋ฌดํ•œ๋Œ€๋ณด๋‹ค ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” 1์ด ๋œ๋‹ค.

์ด๋ฒˆ ๋ฐ˜๋ณต์—์„œ ๊ฐฑ์‹ ๋œ ๋ชจ๋“  ์ •์ ๋“ค์€ ์ด์ „ ๊ฒฝ๋กœ๊ฐ€ 4๋กœ ๊ฐฑ์‹ ๋œ๋‹ค.

Phase 6 (k = 5)

๋งˆ์ง€๋ง‰์œผ๋กœ ์ •์  5๋ฅผ ๊ฒฝ์œ ํ•˜๋Š” ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ„์‚ฐํ•ด๋ณด์ž

  1. d[1][2] ๋Š” d[1][5] + d[5][2] = -4 + 5 = 1 ์ด ๊ธฐ์กด ์ตœ๋‹จ๊ฒฝ๋กœ์ธ 3๋ณด๋‹ค ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” 1์ด ๋œ๋‹ค.
  2. d[1][3] ์€ d[1][5] + d[5][3] = -4 + 1 = -3 ์ด ๊ธฐ์กด ์ตœ๋‹จ๊ฒฝ๋กœ์ธ -1๋ณด๋‹ค ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” -3์ด ๋œ๋‹ค.
  3. d[1][4] ๋Š” d[1][5] + d[5][4] = -4 + 6 = 2 ๊ฐ€ ๊ธฐ์กด ์ตœ๋‹จ๊ฒฝ๋กœ์ธ 4๋ณด๋‹ค ์ž‘๊ธฐ ๋•Œ๋ฌธ์— ์ตœ๋‹จ๊ฑฐ๋ฆฌ๋Š” 2๊ฐ€ ๋œ๋‹ค.