내 잡다한 노트
그래프의 정점끼리의 최단 경로 알고리즘 분류 본문
* 그래프에서 정점끼리의 최단 경로를 구하는 방법
1. 하나의 정점에서 다른 하나의 정점까지의 최단경로를 구하는 문제
start가 하나, arrival point가 하나
2. 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제
start가 하나, arrival point가 여러개
3. 하나의 목적지로 가는 모든 최단 경로를 구하는 문제
start가 여러개, arrival point가 하나
4. 모든 최단 경로를 구하는 문제
start가 여러개, arrival point가 여러개
플로이드 와샬은 마지막에 해당하는 모든 최단 경로를 구하는 방법이다.
다익스트라와 벨만포드는 두 번째에 해당.
'알고리즘' 카테고리의 다른 글
| 다익스트라(Dijkstra) 알고리즘 (0) | 2023.03.09 |
|---|---|
| 희소 배열 (Sparse Table) (0) | 2022.07.06 |
| 트리, 최소공통조상(LCA, Lowest Common Ancestor) (0) | 2022.06.27 |
| Trie 트라이 알고리즘 (0) | 2022.05.14 |
| 동적 프로그래밍 D (0) | 2022.05.06 |