목록플로이드 와샬 (1)

춤추는 개발자

[그래프] 플로이드 와샬 알고리즘

플로이드 와샬 - '모든 정점'으로부터 다른 '모든 정점'까지 이동하는 최단 경로를 구하는 알고리즘 - 다익스트라와의 차이점은 특정한 하나의 정점이 아닌 '모든 정점'이라는 것입니다. - 해당 알고리즘은 기본적으로 '특정 노드를 거쳐가 다른 노드로 이동'이라는 특징이 있습니다. (k - i - j) - 핵심 아이디어는 '거쳐가는 정점'을 기준으로 최단 거리를 구하는 것! www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net public static void cal..
Developer's_til/자료구조 & 알고리즘 2021. 3. 29. 17:55
이전 Prev 1 Next 다음