벨만포드에 이어서 최단경로를 찾는 알고리즘 중 하나다 최소스패닝트리 알고리즘과 비슷하게 check 배열을 둬서, 선택된 인덱스와 선택되지 않는 인덱스를 비교해서 그 거리를 계속 갱신해주는 형태다 따라서 모든 정점을 check 해야므로 V의 시간이 걸리고, check 해야하는 인덱스를 고르기 위해 모든 정점을 탐색해야므로 V의 시간이 덤으로 걸린다 따라서 다익스트라의 시간복잡도는 O(V*V)가 된다 1. check 되어있지않은 정점 중 가장 거리가 짧은 정점을 선택한다 2. 선택된 정점에 대해서 거리를 update한다

dfs로 사이클을 추적할 때 총 3가지의 경우가 나올 수 있다 1. 시작점에서 이루는 정상적인 사이클이 생성 2. 시작점 이후의 다른 점에서부터 사이클이 생성 3. 마지막 점에서만 사이클이 생성 4. 마지막 점에 도달했을 때 마지막 점이 다른 사이클에 속해있을 때

https://github.com/surinoel/boj/blob/master/1922_kruskal.cpp

https://noel-embedded.tistory.com/329 우선순위 큐 정렬은 먼저, struct 안에 연산자 오버로딩으로 사용할 수 있다 그리고 cmp안의 내용을 해석해보자 [출처] https://en.cppreference.com/w/cpp/container/priority_queue compare의 정의를 보면 우선순위 큐는 큰 것 부터 뽑아내기 때문에 실제 정렬을 이룬 후 맨 앞에 오는 요소는 실제로 마지막에 나오는 요소라고 되어있다 따라서 실제로 오름차순으로 뽑고 싶다면, 내림차순으로 정렬을 해야만 뒤에 있는 요소가 제일 작은 수이기 때문에 작은 수부터 나오게 된다

최소 스패닝 트리를 구하는 알고리즘 중 하나. 최소 스패닝 트리는 사이클이 없는 트리의 형태로 만들고, 간선의 가중치가 최소가 되는 형태를 말한다 프림 알고리즘은 총 4가지의 단계로 구성된다 1. 시작 정점을 잡고 큐에 넣는다 2. 큐에서 pop하고, 해당 정점과 간선을 조사하면서 최소값을 고른다 3. 선택한 간선은 큐에 넣는다 4. 2번을 반복 최솟값을 가지는 간선을 찾기 위해서 매번 정렬을 해야기 때문에 힙으로 구성된 우선순위 큐를 사용하는 것이 시간복잡도에서 뛰어나게 된다 모든 정점에 대해서 살펴봐야 하므로 O(V) 간선을 탐색하는데 힙을 사용하므로 O(logE), 따라서 프림 알고리즘의 시간 복잡도는 O(VlogE)

이미 정렬되어있는 힙 기반의 priority_queue를 사용하자. 삽입과 삭제 모두 logN으로 빠른 시간을 가지고 있다 예시문제: https://www.acmicpc.net/problem/15903 https://github.com/surinoel/boj/blob/master/15903.cpp