[알고리즘] 다익스트라

다익스트라 알고리즘이란?

다익스트라 알고리즘은 최단 경로 문제를 푸는 데에 사용되며, 대표적으로 가중치가 있는 그래프에서 노드 간 최단 거리를 찾는 데에 활용됩니다. 이 알고리즘은 1956년에 프레드릭 웹스터 다익스트라에 의해 개발되었으며, 그 존재 이후로 컴퓨터 네트워크, 길 찾기 애플리케이션, 라우팅 프로토콜 등 다양한 분야에서 중요한 역할을 하고 있습니다.

다익스트라 알고리즘의 핵심 아이디어는 출발 노드에서부터 각 노드까지의 최단 거리를 차례대로 구하는 것입니다. 이를 위해 우선순위 큐를 사용하여 최단 거리가 가장 짧은 노드를 선택하고, 해당 노드와 연결된 인접한 노드들의 최단 거리를 업데이트하는 방식으로 동작합니다.

다익스트라 동작 방식

아래 그림은 다익스트라 알고리즘의 동작을 시각적으로 보여주는 예시입니다.

초기 상태

• 출발 노드에서 출발하여 최단 거리는 0으로 설정됩니다.

단계 1:

• 출발 노드와 직접 연결된 노드들(인접 노드)의 최단 거리를 갱신합니다.
• 이 단계에서는 A와 B까지의 최단 거리가 갱신됩니다.

단계 2:

• 현재까지의 최단 거리가 가장 짧은 노드 B를 선택하고, B와 인접한 노드들의 최단 거리를 업데이트합니다.
• 이 단계에서는 C와 D까지의 최단 거리가 갱신됩니다.

단계 3:

• 현재까지의 최단 거리가 가장 짧은 노드 C를 선택하고, C와 인접한 노드들의 최단 거리를 업데이트합니다.
• 이 단계에서는 D까지의 최단 거리가 갱신됩니다.

단계 4

• 현재까지의 최단 거리가 가장 짧은 노드 D를 선택하고, D와 인접한 노드들의 최단 거리를 업데이트합니다.

알고리즘 완료:

• 모든 노드의 최단 거리가 계산되고, 최종적으로 각 노드까지의 최단 거리가 구해집니다.