프림 알고리즘 Prim's algorithm
최소 신장 트리를 구하는 알고리즘
최소 신장 트리는 N-1개의 간선으로 모든 정점을 연결하되, 간선들의 가중치의 합이 가장 작아야 한다.
프림 알고리즘에서는 시작 정점(아무 정점)과 연결된 간선 중 가중치가 가장 작은 간선을 선택하며 그래프를 구한다. ➡️ 그리디
다익스트라 Dijkstra
특정 정점으로부터 모든 정점까지 최단 경로를 찾는 알고리즘
각 정점 사이의 거리가 최소인 간선을 선택하며 그래프를 구한다. ➡️ 그리디
차이점
두 알고리즘 모두 그리디 방식으로 간선을 선택하는 공통점이 있다.
그러면 뭐가 다를까??????????? 의문이 들었다.
정말 말 그대로 최소 신장 트리 vs 최단 경로 이다..
두 알고리즘 다 정점에 간선의 가중치 또는 경로를 저장하게 되는데, 이때 저장하는 값이 다르다.
프림 알고리즘
각 정점에 자신과 연결된 간선의 가중치를 저장한다.
어느 정점에서 시작해도 같은 그래프를 도출한다.
다익스트라 : 시작점 s로부터 모든 정점까지의 최단 경로
각 정점에 시작점으로부터의 경로를 저장한다.
❗️특정 정점으로부터의 최단 경로를 구하기 때문에 시작 정점이 바뀔때마다 최단 경로 그래프가 다르게 도출된다.
정리하고보니 정말 당연한 말이었지만 공부하다보니 헷갈렸다.
둘 다 그리디라면 각 정점에서 최적의 선택(정점과 연결된 간선들 중 가중치/거리가 가장 작은 정점을 선택)을 한다는 것에서 같은데 왜 두 알고리즘이 다르게 쓰일까 궁금했다.
결론
-
다익스트라는
경로이기 때문에 합이 누적되고, 누적 값과 간선으로 다음 정점을 고른다는 것이 달랐다! -
또, 다익스트라는 시작점에 따라 결과가 다르게 도출되지만, 프림 알고리즘은 MST이기 때문에 어느 정점에서 시작해도 결과가 같다는 것이 달랐다!
아...... 어려웠다..........
하지만...!... 해냈어...........
하우에버!! 힘들었어.................................
네버더레스!!!!!!!! 포기하지안아......
