백준 11403 경로찾기

 

 

 

 

 

플로이드 와샬알고리즘을 이용해서,

경로 i -> k와 k -> j 가 존재한다면, 경로 i -> j도 존재하도록 하는것이 핵심이다.

 

 

 

 

 

 

플로이드-와샬?

 

모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 와샬 알고리즘을 사용해야 한다.

Key point는 '거쳐가는 점'을 기준으로 최단거리를 구하는것!

플로이드 와샬은 다이나믹 알고리즘을 사용한다.

 

 

자세한 설명은 아래 사이트를 참고하였다.

 

https://blog.naver.com/ndb796/221234427842

24. 플로이드 와샬(Floyd Warshall) 알고리즘