알고리즘/다익스트라 (dijkstra) (1) 썸네일형 리스트형 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘 : 한 정점에서 다른 정점들로 가는 최단경로를 구하는 알고리즘 그냥 기본적인 알고리즘은 노드를 선택할 때 계속 최단 거리의 노드를 찾아주어야 하기에 O(n^2) 시간복잡도가 걸린다. 그렇기에 넣을 때 logn시간이 걸리는 priority_queue를 사용하면 O(nlogn)시간 복잡도로 줄일 수 있다. 그렇기에 현재 코드는 priority_queue로 구현 하였다. 1. 시작노드에서부터 해당 노드로의 최단 거리(배열에 저장된 거리) 중 가장 짧은 노드 선택.(전에 선택된 것들 제외) 2. 선택된 노드에서부터 다음 노드로 가는 경로가 배열에 저장된 최단 경로보다 작으면 갱신 3. 1-2를 끝날 때까지 반복 1. 최단 거리가 갱신될 때마다 pre배열에 그 전 노드를 기록해둠. 2. 나중에.. 이전 1 다음
