Sean :: Dev

Dijkstra Algorithm 그래프의 한 노드에서 다른 노드로 가는 최단거리를 구하는 알고리즘 (만약 모든 노드 쌍간의 최단거리를 구할땐, n개의 각 정점에 대해 Dijkstra Alg를 여러번 수행해야하므로, 이때는 Floyd-Warshall Alg이 더 유리하다) 동작과정은 BFS와 비슷하지만, Queue가 아닌 Priority Queue를 이용한다. 시간복잡도=O(ElogE) 해당노드까지의 최단거리를 저장할 distance[] 배열 준비후, 미방문을 의미하는 -1로 초기화한다. 노드1에서 시작한다면, 이때까지 자기자신 1까지의 거리는 0이므로 distance[1]에 0을, pq에 (1,0)을 넣는다. 2의10보다 가깝다. distance[2]=8로 갱신, pq에도 (2,8) 넣는다. pq엔 (..