๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์ตœ๋‹จ๊ฒฝ๋กœ์•Œ๊ณ ๋ฆฌ์ฆ˜1

16-3๊ฐ•. ์ตœ๋‹จ๊ฒฝ๋กœ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (Shortest Path Algorithm) (3) ์ด์ „ ๊ฐ•์ขŒ ์ฒจ๋ถ€,, 16-3๊ฐ•. ์ตœ๋‹จ๊ฒฝ๋กœ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (Shortest Path Algorithm) (3) ์ด์ „ ๊ฐ•์ขŒ,,, Bellman-Ford Algo- ๋‚˜ Dijkstra Algo-๋Š” one-to-all ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด์—ˆ๋‹ค. ์ด๋ฒˆ ๊ฐ•์ขŒ์—์„œ๋Š” all-to-all ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๋Œ€ํ•ด ๊ณต๋ถ€ํ•œ๋‹ค. all-to-all ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํ•˜๋‚˜๊ฐ€ Floyd Algorithm ํ˜น์€ Floyd-Warshall Algorithm์ด๋‹ค. Floyd-Warshall ์•Œ๊ณ ๋ฆฌ์ฆ˜ - ๊ฐ€์ค‘์น˜ ๋ฐฉํ–ฅ ๊ทธ๋ž˜ํ”„ G=(V, E), V={1, 2, ..., n} (๋…ธ๋“œ๋“ค์—๋Š” 1๋ฒˆ๋ถ€ํ„ฐ n๋ฒˆ๊นŒ์ง€ ๋ฒˆํ˜ธ๊ฐ€ ๋ถ™์–ด ์žˆ๋‹ค..) - ๋ชจ๋“  ๋…ธ๋“œ ์Œ๋“ค ๊ฐ„์˜ ์ตœ๋‹จ๊ฒฝ๋กœ์˜ ๊ธธ์ด๋ฅผ ๊ตฌํ•จ - d์˜ k์Šน[i, j] ใ„ด ์ค‘๊ฐ„์— ๋…ธ๋“œ์ง‘ํ•ฉ {1, 2, ..., k}์— ์†ํ•œ ๋…ธ๋“œ๋“ค๋งŒ ๊ฑฐ์ณ์„œ ๋…ธ.. 2021. 1. 10.

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”