백준/플로이드 워셜
-
11404 플로이드백준/플로이드 워셜 2024. 6. 25. 14:49
1. 플로이드 워셜 알고리즘에 대해 설명하자면,모든 정점에서 모든 정점으로의 최단경로를 구하고 싶을 때 사용한다.=> 거쳐가는 정점 기준으로 알고리즘 수행=> 음수 순환 사이클이 없는 그래프에서 수행 2. 다익스트라 알고리즘은, 하나의 정점에서 출발하여 다른 모든 정점으로의 최단경로 구함. 그러면 플로이드 워셜 알고리즘에 대해 알아보자. 1. 첫번째 맨 처음에 직행으로 갈 수 있는 경로를 구하면, 아래 표와 같다.갈 수 있는 경로가 없다면, 무한(큰 값)으로 둔다. 1->1, 2->2, 3->3 즉 본인에서 본인으로 가는 경로는 0으로 한다. 1231011210435무한0 2. 두번째 - 정점 1을 경유하여,위에서 플로이드 워셜 알고리즘은 거쳐가는 정점 기준으로 수행한다고 했다. 정점..