[알고리즘] Prim VS Dijkstra, 프림 다익스트라 차이점

Prim VS Dijkstra

두 알고리즘은 동작 방식은 비슷하지만 사용의 목적이 다르다.

특징	프림 알고리즘	다익스트라 알고리즘
목적	최소 신장 트리(MST) 생성	출발점으로부터 각 노드까지의 최단 경로 탐색
비슷한 알고리즘	Kruskal	벨만 포드, 플로이드 와샬
결과	모든 노드를 최소 비용으로 연결하는 트리	출발 노드에서 다른 노드로 가는 최단 거리
간선의 가중치	음수 간선 허용 가능	음수 간선 허용 불가
시작점	시작점은 임의의 노드여도 무관	출발점이 명확하게 정해져야 함
중간 목표	매 단계에서 MST에 포함되지 않은 가장 비용이 적은 간선을 선택	매 단계에서 출발점으로부터 최단 거리 노드를 선택
동작 방식	1. 특정 노드를 MST에 추가 2. 해당 노드(MST 대표)에서 다른 노드들 까지의 거리를 구함 -> dist[] 3. dist[] 기준 가장 가까이 있고 MST에 속해 있지 않은 정점(nearest) 찾음 4. nearest를 집합에 추가 5. (MST에 속한 노드 ~ 속하지 않은 노드)들 사이의 거리가 nearest를 경유했을 때 더 짧아지는게 있다면 dist[] 갱신 6. 3~5를 반복	1. 시작 정점을 기준으로 모든 노드에 대한 거리를 구함 -> dist[] 2. dist[] 중 최단 거리에 있는 노드 (nearest) 찾음 3. nearest를 루트에 추가 4. (시작 노드 ~ 다른 노드)들 사이의 거리(=dist[])가 nearest를 경유했을 때 더 짧아지는게 있다면 dist[] 갱신 5. 2~4를 반복