Algorithm) Floyd-Warshall(ํ”Œ๋กœ์ด๋“œ-์›Œ์…œ) ์•Œ๊ณ ๋ฆฌ์ฆ˜

ํ”Œ๋กœ์ด๋“œ ์›Œ์…œ(Floyd-Warshall)์€ ๋ชจ๋“  ์ง€์ ์—์„œ ๋‹ค๋ฅธ ๋ชจ๋“  ์ง€์ ๊นŒ์ง€์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ๋ชจ๋‘ ๊ตฌํ•ด์•ผ ํ•˜๋Š” ๊ฒฝ์šฐ ์— ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๋งค๋ฒˆ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๋…ธ๋“œ ์ค‘์—์„œ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ–๋Š” ๋…ธ๋“œ๋ฅผ ์ฐพ์„ ํ•„์š”๊ฐ€ ์—†๋‹ค๋Š” ์ ์ด ๋‹ค์ต์ŠคํŠธ๋ผ์™€ ๋‹ค๋ฅธ ์ ์ด๋‹ค. ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜๊ฐ€ n ๊ฐœ์ผ๋•Œ n ๋ฒˆ์˜ ๋‹จ๊ณ„๋ฅผ ์ˆ˜ํ–‰ํ•˜๋ฉฐ ๋‹จ๊ณ„๋งˆ๋‹ค O(N²) ์˜ ์—ฐ์‚ฐ์„ ํ†ตํ•ด ํ˜„์žฌ ๋…ธ๋“œ๋ฅผ ๊ฑฐ์ณ๊ฐ€๋Š” ๋ชจ๋“  ๊ฒฝ๋กœ๋ฅผ ๊ณ ๋ คํ•œ๋‹ค. ๊ทธ๋ž˜์„œ ์ด ์‹œ๊ฐ„ ๋ณต์žก๋„๋Š” O(N³)์ด๋‹ค. ์ฆ‰, ๋ชจ๋“  ์ง€์ ์„ ์‹œ์ž‘์œผ๋กœ ์‚ผ๊ณ  ๋ชจ๋“  ์ง€์ ์— ๋Œ€ํ•ด์„œ ๋์œผ๋กœ ์‚ผ์•„์„œ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋Š”๋ฐ ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ๊ฒฝ์œ ์ง€๋กœ ์‚ผ๋Š” ๊ณผ์ •์ธ n ๋ฒˆ์˜ ๋‹จ๊ณ„๋ฅผ ์ˆ˜ํ–‰ ํ•œ๋‹ค. min(์‹œ์ž‘ → ๋, ์‹œ์ž‘ → ๊ฒฝ์œ  + ๊ฒฝ์œ  → ๋) ๋ฅผ ๊ตฌํ•˜๋Š” ๊ฒƒ์ด๋‹ค. ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์ถœ๋ฐœ ๋…ธ๋“œ๊ฐ€ 1๊ฐœ์ด๋ฏ€๋กœ ๋‹ค๋ฅธ ๋ชจ๋“  ๋…ธ..

Algorithm 2022. 8. 31. 17:05
์ตœ๊ทผ์— ์˜ฌ๋ผ์˜จ ๊ธ€
์ตœ๊ทผ์— ๋‹ฌ๋ฆฐ ๋Œ“๊ธ€
๊ธ€ ๋ณด๊ด€ํ•จ
ยซ   2024/12   ยป
์ผ ์›” ํ™” ์ˆ˜ ๋ชฉ ๊ธˆ ํ† 
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
๋งํฌ
Total
Today
Yesterday