다익스트라 알고리즘 편집하기

다익스트라 알고리즘(Dijkstra algorithm, 다익스트라 算法)은 그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 찾는 알고리즘이다.
==개요==
다익스트라 알고리즘은 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger W. Dijkstra)가 1956년에 고안하고 1959년에 발표한 알고리즘이다. 가중치가 있는 방향 또는 무방향 그래프에서 음의 가중치가 없는 경우에 사용할 수 있으며, 시작 정점에서 다른 모든 정점까지의 최단 경로를 효율적으로 계산할 수 있다.
==동작 원리==
다익스트라 알고리즘은 다음과 같은 방식으로 작동한다.
*모든 정점의 거리를 무한대로 초기화하고, 시작 정점의 거리를 0으로 설정한다.
*아직 방문하지 않은 정점 중에서 거리 값이 가장 작은 정점을 선택한다.
*선택된 정점과 인접한 정점들의 거리 값을 갱신한다.
*모든 정점을 방문할 때까지 이 과정을 반복한다.
이 알고리즘은 우선순위 큐를 활용하면 시간 복잡도를 효율적으로 줄일 수 있다. 일반적인 구현에서는 최소 힙(min-heap)을 이용한 우선순위 큐를 사용하여 O((V+E)logV)의 시간 복잡도를 가진다.
==예시==
다음은 가중치가 있는 그래프에서 시작 정점 A에서 다른 모든 정점까지의 최단 경로를 구하는 예이다.

그래프:
 A --(4)--> B --(1)--> C
  \         |
  (2)       (2)
   \        v
    >------>D
==단계별 계산==
다익스트라 알고리즘을 통해 A에서 시작해 모든 정점까지의 최단 경로를 구하는 과정을 표로 나타내면 다음과 같다.
{| class="wikitable"
!단계!!방문한 정점!!A까지 거리!!B까지 거리!!C까지 거리!!D까지 거리!!비고
|-
|0||없음||0||∞||∞||∞||초기화
|-
|1||A||0||4||∞||2||A → B(4), A → D(2)
|-
|2||D||0||4||∞||2||D → B(4), B는 기존 거리 유지
|-
|3||B||0||4||5||2||B → C(4+1=5)
|-
|4||C||0||4||5||2||완료
|}최종적으로 각 정점까지의 최단 거리는 다음과 같다:
*A: 0
*B: 4
*C: 5
*D: 2
==구현==
다익스트라 알고리즘은 다양한 프로그래밍 언어로 구현할 수 있으며, 대표적인 Python 구현은 다음과 같다.<syntaxhighlight lang="python">
import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [(0, start)]

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        if current_distance > distances[current_node]:
            continue

        for adjacent, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, (distance, adjacent))

    return distances
</syntaxhighlight>
==응용==
다익스트라 알고리즘은 다음과 같은 분야에서 활용된다.
*GPS 내비게이션 시스템
*네트워크 라우팅 프로토콜 (예: OSPF)
*게임의 경로 탐색 시스템
*물류 및 운송 경로 최적화
==한계==
다익스트라 알고리즘은 음의 가중치를 가진 간선이 포함된 그래프에서는 사용할 수 없다. 이러한 경우에는 벨만-포드 알고리즘을 사용해야 한다.
==같이 보기==
*[[벨만-포드 알고리즘]]
*[[A* 알고리즘]]
*[[최단 경로 문제]]
*[[그래프 이론]]
*[[우선순위 큐]]
==참고 문헌==
*Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. *Numerische Mathematik*, 1(1), 269–271.
==각주==
[[분류:알고리즘]]
[[분류:그래프 이론]]