모든 정점간 최단거리를 구해내는 알고리즘
O(V^3)
벨만 포드로 모든 정점간 최단거리를 구하려면 O(V^2 * E) 이므로 벨만포드보다 빠르다.
필요한 것:
dist[MAX][MAX] = {입력값 | 연결안됐으면INF}
for(int k=0; k<n; k++)
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j];
기본문제
https://www.acmicpc.net/problem/11404
11404번: 플로이드
첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 시작
www.acmicpc.net
'알고리즘 > 메모' 카테고리의 다른 글
| 위상정렬, DAG(Directed Acyclic Graph) (0) | 2019.08.18 |
|---|---|
| 최소 스패닝 트리 (0) | 2019.08.18 |
| 벨만포드, SPFA (0) | 2019.08.18 |
| 다익스트라 (0) | 2019.08.18 |
| 에라토스테네스, 소수 (0) | 2019.08.18 |
