모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산
다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 수행
다만 매 단계마다 방문하지 않은 노드 중에 최단거리를 갖는 노드를 찾는 과정이
필요하지는 않음
2차원 테이블에 최단 거리 정보를 저장
다이나믹 프로그래밍 유형에 속함
각 단계마다 특정한 노드 K를 거쳐가는 경우를 확인
A에서 B로 가는 최단 거리보다 A에서 K를 거쳐 B로 가는 거리가 더 짧은지 검사
점화식
D ab = min(D ab, D ak + D kb)
시간 복잡도가 O(N*2)이기 때문에 N의 크기가 500이하 일때 사용
노드를 거쳐가는 문제일 때 사용
ex) 백준 11404번 11403번
'알고리즘' 카테고리의 다른 글
| 배낭 문제 (Knapsack Problem) (0) | 2022.01.22 |
|---|---|
| 0-1 BFS (0) | 2022.01.19 |
| 다익스트라 최단경로 (Dijkstra) (0) | 2022.01.19 |
| 다이나믹 프로그래밍 (Dynamic programming) (0) | 2022.01.19 |
| 구현 (Implementation) (0) | 2022.01.19 |