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

프림 : 그래프상에 존재하는 모든 노드들을 최소비용으로 연결시키는 알고리즘 다익스트라 : 특정 시작 노드 로부터 그래프 상에 존재하는 모든 노드, 즉 두 노드 사이의 최단거리를 구하는 알고리즘 -공통점 BFS 알고리즘과 유사하지만 BFS랑 다르게 방문할 때 해당 visited 배열 인덱스에 true를 마킹한다. (bfs때는 중복 수행을 막기 위해서 그냥 해당 노드 큐에 넣는 동시에 true를 마킹해버린다.) -차이점 1. 프림은 다익스트라와 달리 두 노드 사이가 최단거리가 아닐 수도 있다. ※ 프림은 1->3의 비용이 3인 반면에, 다익스트라는 1->3의 비용이 2이다. 2. 프림은 무향 그래프에서만 작동하고, 다익스트라는 무향, 유향 그래프에서 모두 작동한다. 3. 프림이 다익스트라를, 다익스트라가 프..
Algorithm 2021. 9. 26. 02:05
1