지금 코딩 문제를 푸는게 다익스트라 알고리즘을 사용해야하는지 플로이드 와샬 알고리즘을 사용해야 하는지가 문제이다.
자료 검색을 했는데 추상적으로만 알 것 같아서 내가 직접 정리하면서 알아보는 시간을 가져보겠다.
다익스트라 : 하나의 정점 -> 다른모든 정점 (최단경로)
플로이드와샬 : 모든정점 -> 다른모든 정점(최단경로)
다익스트라는 BFS 형태를 가지고 있다. 또한 너비 우선 탐색처럼 시작점에서 가까운 순서대로 정점을 방문해간다. 가중치가 있는 그래프에서는 너비 우선 탐색을 그대로 적용할 수 없기에 우선순위 큐를 이용하여 이를 해결한다.
'알고리즘' 카테고리의 다른 글
| 프로그래머스 - 두 큐 합 같게 만들기(JAVA) (0) | 2022.11.13 |
|---|---|
| 백준 1238 파티 (JAVA) (0) | 2022.11.11 |
| 백준 1967 트리의 지름(JAVA) (1) | 2022.11.10 |
| 백준 1149번 RGB 거리 (JAVA) (2) | 2022.11.09 |
| 백준 1920번 수 찾기 (JAVA) (0) | 2022.11.09 |