플로이드-와샬 알고리즘(이하 플로이드 알고리즘)은 최단 경로를 구하는 알고리즘이다.
이미 잘 알고있는 다익스트라 알고리즘은 한 점점으로 부터 다른 모든 정점으로의 최단 거리를 구할 수 있다.
하지만 플로이드 알고리즘은 모든 정점으로부터 모든 정점으로의 최단 거리를 구하는 알고리즘이다.
기본적으로 그래프를 일단 나타내고, 순차적으로 어떠한 정점을 거쳤을 때, 이동하는 비용이 줄어든다면 값을 고치는것을 반복하는 알고리즘이다.
중요한건 (A에서 B로 가는 거리) > (A에서C를 들렀다가 B로 가는거리)이면 작은 값으로 계속 갱신만 해주면 되는거다.
말로하려니까 어렵다. 아래에 그림을 참고해라.
관련 문제
https://www.acmicpc.net/problem/11404
11404번: 플로이드
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
https://jinniepark.tistory.com/64
[백준][11404]플로이드
/* 문제설명 */ n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도
jinniepark.tistory.com
'Coding Test > Algorithm' 카테고리의 다른 글
| [알고리즘 기본]다익스트라 알고리즘 (0) | 2021.09.27 |
|---|---|
| [알고리즘 기본]Kruskal 알고리즘 (0) | 2021.09.15 |
| [알고리즘 기본]PRIM 알고리즘 (0) | 2021.08.24 |