백준 플로이드

[baekjoon 11404] 플로이드 (플로이드-와샬) (C++)

www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 기본적인 플로이드 와샬 알고리즘을 사용해서 푸는 문제이다. 다익스트라와 같이 최단 거리를 찾는 알고리즘이지만, 차이점을 한번 비교해보았다. 다익스트라 VS 플로이드-와샬 1. 최단거리를 찾는 경로 - 다익스트라 : 어떤 한 점에서 목적지까지의 최단 거리를 업데이트 - 플로이드 : 모든 정점에서 모든 정점까지의 최단 거리 -> 단일 경로의 최단 거리를 찾는 것은 다익스트라가 훨씬 빠르다. 2. 최단 거리를 찾는 ..