์ฝ๋ฉํ
์คํธ/๊ธฐ๋ณธ ์๊ณ ๋ฆฌ์ฆ
2022. 2. 24.
์ต๋จ๊ฑฐ๋ฆฌ (improved_dijkstra)
improved_dijkstra ๊ฐ๋จํ ๋ค์ต์คํธ๋ผ๋ O(v^2)์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ ธ ๋
ธ๋์ ๊ฐ์๊ฐ 10000๊ฐ๋ฅผ ๋์ด๊ฐ๋ฉด ํ์๊ฐ ์๋ค. ํ์ง๋ง ๊ฐ์ ๋ ๋ค์ต์คํธ๋ผ๋ ์ต์
์ ๊ฒฝ์ฐ์๋ O(ElogV)๋ฅผ ๋ณด์ฅํ์ฌ ํด๊ฒฐํ ์ ์๋ค. (V๋ ๋
ธ๋์ ๊ฐ์, E๋ ๊ฐ์ ์ ๊ฐ์) ๊ธฐ์กด ๊ฐ๋จํ ๋ค์ต์คํธ๋ผ๋ ์ต๋จ๊ฑฐ๋ฆฌ๋ฅผ ์์์๋ถํฐ ํ๋์ฉ ํ์ธํ๋๋ฐ ์ด๋ฅผ ๋์ฑ ๋น ๋ฅด๊ฒ heap๊ตฌ์กฐ์ ์ฐ์ ์์ ํ๋ก ์ฐพ๋๋ค๋๊ฒ์ด ํต์ฌ ํฌ์ธํธ์ด๋ค. ์ฐ์ ์์ ํ๋ ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋์ ๋ฐ์ดํฐ๋ฅผ ๊ฐ์ฅ ๋จผ์ ์ญ์ ํ๋ค๋ ํน์ง์ด ์๊ณ heapq ๋ผ์ด๋ธ๋ฌ๋ฆฌ๋ฅผ ํตํด ์ฌ์ฉํ๋ค. ์ฐ์ ์์ ํ๋ ์ผ๋ฐ์ ์ผ๋ก ์ ์ํ ์๋ฃํ์ ๋ณ์๋ฅผ ์ฌ์ฉํ๋ฉฐ (๊ฐ์น, ๋ฌด๊ฒ)๋ก ์ด๋ฃจ์ด์ง ๋ฐ์ดํฐ๋ฅผ ์ฐ์ ์์ ํ์ ์ง์ด๋ฃ์ผ๋ฉด ํญ์ ๊ฐ์น๊ฐ ๋์ ๋ฌผ๊ฑด๋ถํฐ ๋จผ์ ๋์ค๊ฒ๋๋ค.(๋ง์ฝ (๋ฌด๊ฒ, ๊ฐ์น)๋ก ..