DFS, BFS, 다익스트라, 플로이드 와샬, 프림 알고리즘 이야기

---

DFS

깊이 우선 탐색.

말 그대로 현재 위치에서 갈 수 있는 곳 중 짧은 곳으로 최대한 깊게 들어간다. 들어가다가 막히면 다시 뒤로 돌아와서 갈 수 있는 곳으로 감.

하지만 만약 그래프의 깊이가 커질수록 부하도 커진다.

BFS

너비 우선 탐색

이건 과거, 그리고 현재에서 갈 수 있던 곳 중 가장 짧은 곳으로 간다. 

DFS, BFS는 이전 값들을 축적하지 않기 때문에 간선을 이동하는 비용(가중치)이 1이어야 한다. (비용이 같아야 한다는 것)

다익스트라 알고리즘

너비 우선 탐색이다.

다익스트라 알고리즘은 이 (가중치)들을 점점 축적해 나간다.

축적한다는 건 다이나믹 방식을 사용한다는 것이다.

프림 알고리즘

프림 알고리즘은 MST(최소 스패닝 트리) 알고리즘이라고 하는데,

각 정점을 연결하는 간선들을 최소로 구성하는 비용을 구하는 것이다.

즉 이것은 최단 거리를 구하는 것은 아니다.

플로이드 와샬 알고리즘

O(n^3)의 복잡도를 가진다..

다익스트라가 어느 한 지점으로부 모든 점으로의 최단거리를 구해나가는 것이라면

이것은 모든 점에서 모든 점으로의 최단거리를 구한다.

현재 가려는 정점까지의 거리가 다른 점들을 거쳐서 가는 것보다 멀다면 거쳐서 가는 거리값을 저장해 나가는 것이다.

다이나믹은 어느 한 지점에서부터 이므로, 만약 여러 위치에서의 최단거리를 빨리 구해내야 한다면,

플로이드 와샬 알고리즘을 사용하는 것이 옳은 방법인 것 같다.