Dijkstra

다익스트라

다익스트라(Dijkstra) 알고리즘은 그래프 내에서 한 지점에서 다른 모든 지점으로의 최단 경로를 찾는 데 사용되는 알고리즘입니다. 이 알고리즘은 너비 우선 탐색(BFS)을 변형한 것으로, 각 노드에 대한 최단 경로를 점진적으로 찾아가는 방식으로 동작합니다.

다익스트라 알고리즘의 핵심 아이디어는 시작 지점으로부터 각 노드까지의 현재까지 발견된 최단 경로를 유지하고, 그 중 가장 짧은 경로를 확장해 나가는 것입니다. 이를 위해 우선순위 큐를 사용하여 현재까지 발견된 최단 경로가 가장 짧은 노드를 먼저 선택하여 탐색합니다.

알고리즘의 간단한 동작 과정은 다음과 같습니다:

시작 노드의 최단 경로를 0으로 초기화하고, 모든 다른 노드의 최단 경로를 무한대로 설정합니다. 시작 노드를 우선순위 큐에 삽입하고, 현재까지 발견된 최단 경로가 가장 짧은 노드를 선택하여 처리합니다. 선택된 노드를 기준으로 인접한 노드들의 최단 경로를 업데이트합니다. 만약 기존에 발견된 최단 경로보다 더 짧은 경로를 찾을 경우, 해당 노드의 최단 경로를 업데이트하고 우선순위 큐에 새로운 최단 경로를 반영합니다. 우선순위 큐가 빌 때까지 위 과정을 반복합니다. 이 과정을 모든 노드에 대해 반복하면, 시작 노드로부터 각 노드까지의 최단 경로가 결정됩니다. 다익스트라 알고리즘은 음의 가중치가 없는 그래프에서 사용될 수 있으며, 시간 복잡도는 O((V + E) log V)입니다. 여기서 V는 노드의 수이고, E는 간선의 수입니다.