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

다익스트라 알고리즘(Dijkstra algorithm, 다익스트라 算法)은 그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 찾는 알고리즘이다.
==개요==
다익스트라 알고리즘은 네덜란드의 컴퓨터 과학자 [[에츠허르 다익스트라|에츠허르 다익스트라(Edsger W. Dijkstra)]]가 1956년에 고안하고 1959년에 발표한 알고리즘이다. 가중치가 있는 방향 또는 무방향 그래프에서 음의 가중치가 없는 경우에 사용할 수 있으며, 시작 정점에서 다른 모든 정점까지의 최단 경로를 효율적으로 계산할 수 있다.

현대에서도 길 찾기, 라우팅 알고리즘 등에 많이 사용된다. 음의 가중치가 있는 그래프에선 동작하지 않는 문제점이 있으나, 실생활에선 음의 가중치가 존재하는 경우가 흔치 않기 때문에 크게 문제되지 않는 경우가 많다.
==동작 원리==
다익스트라 알고리즘은 다음과 같은 방식으로 작동한다.
*모든 정점의 거리를 무한대로 초기화하고, 시작 정점의 거리를 0으로 설정한다.
*아직 방문하지 않은 정점 중에서 거리 값이 가장 작은 정점을 선택한다.
*선택된 정점과 인접한 정점들의 거리 값을 갱신한다.
*모든 정점을 방문할 때까지 이 과정을 반복한다.
이 알고리즘은 우선순위 큐를 활용하면 시간 복잡도를 효율적으로 줄일 수 있다. 일반적인 구현에서는 최소 힙(min-heap)을 이용한 우선순위 큐를 사용하여 O((V+E)logV)의 시간 복잡도를 가진다.
==예시==

=== 기본 예시 ===
다음은 가중치가 있는 그래프에서 시작 정점 A에서 다른 모든 정점까지의 최단 경로를 구하는 예이다.

그래프:
 A --(4)--> B --(1)--> C
  \         |
   \       (2)
    \       v
     (2)--> D
'''단계별 계산'''

다익스트라 알고리즘을 통해 A에서 시작해 모든 정점까지의 최단 경로를 구하는 과정을 표로 나타내면 다음과 같다.
{| class="wikitable"
!단계!!기준점!!B까지 거리!!C까지 거리!!D까지 거리!!비고
|-
|0||A||∞||∞||∞||초기화
|-
|1||A||4||∞||2||A → B(4), A → D(2) 직접 연결됨
|-
|2||D||4||∞||2||
* A와 거리가 가장 가까웠던 D 선택
* D를 거쳐서 더 짧아지는 경로 없음
|-
|3||B||4||5||2||
* 그 다음 A와 거리가 가장 가까웠던 B 선택
* C로 갈 수 있게 됨
|-
|4||C||4||5||2||
* 마지막으로 방문하지 않은 C 선택
* 변동 없음
|}최종적으로 각 정점까지의 최단 거리는 다음과 같다:
*A: 0
*B: 4
*C: 5
*D: 2

=== 좀 더 어려운 예시 ===
[[파일:방향 그래프.png|400x400픽셀]]
{| class="wikitable"
!단계!!기준점
!A!!B!!C!!D
!E
!F
!G
!H!![[우선순위 큐]]
|-
|0||A
|0||∞||∞||∞
|∞
|∞
|∞
|∞||B(∞), C(∞), D(∞), E(∞), F(∞), G(∞), H(∞)


|-
|1||A
|'''(0)'''||1||5||11
|
|
| ||

|B(1), C(5), D(11)


|-
|2||B
| ||'''(1)'''||3||
|11
|
|
| ||C(3), D(11), E(11)


|-
|3||C
| || ||'''(3)'''||
|9
|4
|
| ||F(4), E(9), D(11)




|-
|4||F
| || || ||
|8
|'''(4)'''
|7
|5||H(5), G(7), E(8), D(11)
|-
|5
|H
|
|
|
|
|7
|
|6
|'''(5)'''
|G(6), E(7), D(11)
|-
|6
|G
|
|
|
|7
|
|
|'''(6)'''
|
|E(7), D(7)
|-
|7
|E
|
|
|
|
|'''(7)'''
|
|
|
|D(7)
|-
|8
|D
|
|
|
|'''(7)'''
|
|
|
|
|
|}

=== 음의 값을 넣을 수 없는 예시 ===

==구현==
다익스트라 알고리즘은 다양한 프로그래밍 언어로 구현할 수 있으며, 대표적인 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

graph = {
    'A': {'D': 11, 'C': 5, 'B': 1},
    'B': {'C': 2, 'E': 10},
    'C': {'F': 1, 'E': 6},
    'D': {'C': 3},
    'E': {},
    'F': {'D': 5, 'E': 4, 'G': 3, 'H': 1},
    'G': {'D': 1},
    'H': {'E': 2, 'G': 1}
}

dist = dijkstra(graph, 'A')

print("\nFinal distances from A:")
for node in sorted(dist):
    print(f"{node}: {dist[node]}")
</syntaxhighlight>결과:
 Final distances from A:
 A: 0
 B: 1
 C: 3
 D: 7
 E: 7
 F: 4
 G: 6
 H: 5

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