간선의 가중치가 0 이상인 그래프에서, 하나의 출발점에서 각 정점까지의 최단 경로를 구하는 알고리즘. 거리가 확정되지 않은 정점 중 가장 가까운 것을 확정하고, 그 이웃 정점의 거리를 갱신하는 것을 반복한다. 음의 가중치를 가진 간선이 있으면 올바르게 구할 수 없다.
일본어 명칭: ダイクストラ法
다익스트라 알고리즘(Dijkstra's Algorithm)은(는) 자료 구조와 알고리즘 등 1개 분야의 연습 문제 3개에 나와요.
분야: 자료 구조와 알고리즘
출발점의 거리를 0, 다른 정점을 무한대로 하고, 모든 정점을 미확정으로 합니다. 미확정 정점 중 거리가 최소인 것을 하나 골라 확정하고, 그 정점에서 나가는 간선에 대해 '확정한 거리 + 간선의 가중치'가 그 너머 정점의 현재 거리보다 작으면 갱신합니다(완화). 이것을 모든 정점이 확정될 때까지 반복합니다. 갱신할 때 직전 정점을 기록해 두면, 최단 경로 자체를 나중에 따라갈 수 있습니다.
최소 정점을 매번 모든 정점에서 찾으면 정점 수 V에 대해 O(V²)이 걸립니다. 이진 힙에 의한 우선순위 큐를 사용하면 간선 수를 E라 할 때 O((V + E) log V)가 되어, 도로망처럼 간선이 적은 그래프에서 크게 빨라집니다. 그래프는 인접 리스트로 갖는 것이 보통입니다. 내비게이션의 경로 탐색에서는 목적지까지의 예상 거리를 더해 탐색을 목적지 방향으로 좁히는 A* 탐색이나, 미리 계산한 정보를 사용하는 고속화 기법이 조합되어 있습니다.
다익스트라 알고리즘은 다른 정점을 거치면 거리가 늘어나는 일은 있어도 줄어들지 않는다는 전제로 정점을 확정하므로, 음의 가중치를 가진 간선이 있으면 확정한 거리가 나중에 짧아지는 경우가 있어 올바른 답이 보장되지 않습니다. 음의 가중치가 있는 경우는 모든 간선의 완화를 V−1회 반복하는 벨먼-포드 알고리즘을 사용하며, 음의 사이클 검출도 할 수 있습니다. 모든 정점 쌍의 최단 경로에는 동적 계획법에 의한 플로이드-워셜 알고리즘(O(V³))도 쓰입니다. 네트워크 라우팅에서는 OSPF 등의 링크 상태 방식 프로토콜이 각 라우터에서 다익스트라 알고리즘으로 경로를 계산합니다.
정답: B. S→B→A→C→T, 길이 7
다익스트라 알고리즘은 거리가 확정되지 않은 정점 중 가장 가까운 것을 확정하고, 그 이웃 정점의 거리를 갱신하는 것을 반복합니다. S(0)에서 B가 1로 확정되고, B를 거치면 A는 1 + 2 = 3으로 직접 가는 4보다 짧아집니다. A(3)를 확정하면 C는 3 + 1 = 4, T는 3 + 6 = 9가 되고, C(4)를 확정하면 T는 4 + 3 = 7로 갱신됩니다. 따라서 최단 경로는 S→B→A→C→T이고 길이는 7입니다. S→A→C→T(8)는 S−A를 직접 지나는 만큼 길고, S→B→C→T(9)는 B−C의 5가 크기 때문에 길어집니다.
정답: C. 간선의 가중치가 모두 0 이상일 것
다익스트라 알고리즘은 미확정 정점 중 거리가 가장 작은 것을 확정합니다. 이는 다른 정점을 거치면 거리가 늘어나는 일은 있어도 줄어드는 일은 없다는 전제에 기반합니다. 음의 가중치를 가진 간선이 있으면 나중에 다른 경로로 거리가 짧아지는 경우가 있으며, 예를 들어 S→A가 2, S→B가 3, B→A가 −2인 방향 그래프에서는 A를 2로 확정한 뒤에 S→B→A의 1이 발견됩니다. 음의 가중치가 있을 때는 벨먼-포드 알고리즘 등을 사용합니다. 사이클이 있어도, 간선에 방향이 있어도, 가중치가 0 이상이면 다익스트라 알고리즘을 사용할 수 있습니다.
모든 간선의 가중치가 1이면, 다익스트라 알고리즘은 너비 우선 탐색과 같은 순서로 정점을 확정합니다. 가중치가 다른 경우에 큐 대신 거리가 작은 순서로 꺼내는 우선순위 큐를 사용하도록 일반화한 것이라고 볼 수 있습니다.
쓸 수 있습니다. 가중치가 0 이상이면 방향 그래프든 무방향 그래프든, 사이클이 있어도 올바른 최단 경로가 구해집니다.
다익스트라 알고리즘은 거리가 확정되지 않은 정점 중 가장 가까운 것을 확정하고, 그 이웃 정점의 거리를 갱신하는 것을 반복합니다.
간선에 방향이 없는 그래프에서 간선의 가중치(거리)가 S−A: 4, S−B: 1, A−B: 2, A−C: …다익스트라 알고리즘은 미확정 정점 중 거리가 가장 작은 것을 확정합니다.
다익스트라 알고리즘으로 올바른 최단 경로를 구하기 위한, 그래프에 관한 조건으로 올바른 것은?너비 우선 탐색이나 다익스트라 알고리즘처럼 정점에서 나가는 간선을 차례로 따라가는 처리에서는 인접 리스트가 더 효율적으로 동작합니다.
정점이 100만 개, 간선이 300만 개 정도인 도로망처럼 정점 수에 비해 간선이 적은(희소한) 그래프를 …너비 우선 탐색(Breadth-First Search) 깊이 우선 탐색(Depth-First Search) 동적 계획법(Dynamic Programming) 스택(Stack) 시간 복잡도(Time Complexity) 안정 정렬(Stable Sort) 연결 리스트(Linked List) 이진 탐색 트리(Binary Search Tree) 이진 탐색(Binary Search) 이진 힙(Binary Heap)