프림, kruskal 은 알겠는데 다익스트라는 뭔가요

[ㅇ(223.62)]

젤 짧은길 구하는거 프림이랑 k배윗는데

다익스트라라는 요상한게튀어나왓어요 이건머가다른가요

[ㅣ(223.62)]

셋다 최고짧은거리 구하는거아니에요?

[ㅣ(223.62)]

근데 답이 다른데 다익스트란가머시긴

[고라니(39.7)]

64비트 드렸습니다

[dddd(220.70)]

알고리즘 구현 과정은 다익스트라랑 프림이랑 비슷함, 차이점은 프림은 임의의 점에서 시작하는거고 다익스트라는 출발점이 주어져야함.

[dddd(220.70)]

프림은 선분을 추가 할 때, 현재 정해진 상태 트리 기준으로 가장 가까운 점을 추가 시키지만, 다익스트라는 출발점으로부터 가장 가까운 점을 추가시켜야함

[dddd(220.70)]

예를 들어 프림은 1->3 이렇게 트리가 되잇으면 3->4, 3->5중 3->5 더 가까우면 3->5가 선택됨.

[dddd(220.70)]

다익스트라는 1->3 이렇게 있고 3->4 3->5 있으면 1->3->4, 1->3->5 이렇게 출발점부터 고려하여 가까운 점을 선택함