///////
Search
Duplicate

Dijkstra

Summary

Dijkstra(다익스트라) - Shortest path 탐색 알고리즘

Description

다이나믹 프로그래밍 또는 그리디 알고리즘으로 만들 수 있음
1.
출발 노드를 설정
2.
출발 노드를 기준으로 각 노드의 최소 비용을 저장
3.
방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택
4.
해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱심
5.
위 과정에서 3~4를 반복.
다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘.
한 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌.
이때 음의 간선을 포함할 수는 없음.
현실 세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라는 현실 세계에 사용하기 매우 적합한 알고리즘 중 하나.
하나의 최단거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용.

Data Structure

Heap

Time Complexity

선형 탐색 ⇒ O(N^2)
힙 ⇒ O(N log N)

Code