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.