๋ฌธ์ ์ค๋ช ๊ฐ์ฒ ๋ถ๋์ ๊ฐ ๋ถ๋์์ด ์ฌ๋ฌ ์ง์ญ์ ๋ฟ๋ฟ์ด ํฉ์ด์ ธ ํน์ ์๋ฌด๋ฅผ ์ํ ์ค์ ๋๋ค. ์ง๋์์ ๊ฐ์ฒ ๋ถ๋๊ฐ ์์นํ ์ง์ญ์ ํฌํจํ ๊ฐ ์ง์ญ์ ์ ์ผํ ๋ฒํธ๋ก ๊ตฌ๋ถ๋๋ฉฐ, ๋ ์ง์ญ ๊ฐ์ ๊ธธ์ ํต๊ณผํ๋ ๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ๋ชจ๋ 1๋ก ๋์ผํฉ๋๋ค. ์๋ฌด๋ฅผ ์ํํ ๊ฐ ๋ถ๋์์ ์ง๋ ์ ๋ณด๋ฅผ ์ด์ฉํ์ฌ ์ต๋จ์๊ฐ์ ๋ถ๋๋ก ๋ณต๊ทํ๊ณ ์ ํฉ๋๋ค. ๋ค๋ง ์ ๊ตฐ์ ๋ฐฉํด๋ก ์ธํด, ์๋ฌด์ ์์ ๋์ ๋ค๋ฅด๊ฒ ๋๋์์ค๋ ๊ฒฝ๋ก๊ฐ ์์ด์ ธ ๋ณต๊ท๊ฐ ๋ถ๊ฐ๋ฅํ ๋ถ๋์๋ ์์ ์ ์์ต๋๋ค. ๊ฐ์ฒ ๋ถ๋๊ฐ ์์นํ ์ง์ญ์ ํฌํจํ ์ด์ง์ญ์ ์ n, ๋ ์ง์ญ์ ์๋ณตํ ์ ์๋ ๊ธธ ์ ๋ณด๋ฅผ ๋ด์ 2์ฐจ์ ์ ์ ๋ฐฐ์ด roads, ๊ฐ ๋ถ๋์์ด ์์นํ ์๋ก ๋ค๋ฅธ ์ง์ญ๋ค์ ๋ํ๋ด๋ ์ ์ ๋ฐฐ์ด sources, ๊ฐ์ฒ ๋ถ๋์ ์ง์ญ destination์ด ์ฃผ์ด์ก์ ๋, ์ฃผ์ด์ง sourc..