프림 VS 다익스트라 알고리즘

프림 : 그래프상에 존재하는 모든 노드들을 최소비용으로 연결시키는 알고리즘

프림 알고리즘 적용

 

다익스트라 : 특정 시작 노드 로부터 그래프 상에 존재하는 모든 노드, 즉 두 노드 사이의 최단거리를 구하는 알고리즘

 

 

다익스트라 알고리즘 적용

-공통점 

BFS 알고리즘과 유사하지만 BFS랑 다르게 방문할 때 해당 visited 배열 인덱스에 true를 마킹한다. (bfs때는 중복 수행을 막기 위해서 그냥 해당 노드 큐에 넣는 동시에 true를 마킹해버린다.)

 

-차이점

1. 프림은 다익스트라와 달리 두 노드 사이가 최단거리가 아닐 수도 있다.

   ※ 프림은 1->3의 비용이 3인 반면에, 다익스트라는 1->3의 비용이 2이다.

2. 프림은 무향 그래프에서만 작동하고, 다익스트라는 무향, 유향 그래프에서 모두 작동한다.

3. 프림이 다익스트라를, 다익스트라가 프림을 보장해주지 않는다.

   -> 최소스패닝트리가 최단경로트리를, 최단경로트리가 최소스패닝트리를 보장하지 않는다.