다익스트라 알고리즘(Dijkstra’s Algorithm)은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다.
주로 인공위성 GPS 소프트웨어나 네트워크 라우팅 등에 사용된다. 보다 실생활에 밀접하게는 네비게이션의 두 도시를 잇는 가장 빠른 길을 찾는데 사용될 수 있다.
2. 특징
1개의 출발점에서 1개의 도착지까지 가는 최소 비용 경로를 알기 위해 1개의 출발점에서 모든 도착점까지 가는 최소 비용 경로를 찾는다.
원하는 도착지에 도달하면 알고리즘을 종료한다.
경로의 비용이 작은 순서대로 찾는다.
경로의 비용은 항상 0 이상이라고 가정한다.
경로의 비용이 가장 작은 경우는 자기 자신으로 가는 경로이다.
모든 노드의 식별자와 비용 정보는 알려져 있다.
용어 정의
D(n): n으로 가는데 드는 비용(길이)
시작점에서 n까지 한 번에 갈 수 없을 경우(이웃이 아닐 경우) 포워딩 테이블에는 그 비용이 무한으로 표시된다.
p(n): 시작점에서 n까지 가는 최소 비용 경로에서 n의 직전 노드
N’: 이미 최단 경로를 찾은 노드의 집합
3. 경로 구하기
u에서 출발해 모든 노드로 가는 최소비용 경로를 알아보자.
이 그래프에서 노드 u로부터의 최소 비용 경로 그래프
4. 시간 복잡도
가장 작은 간선의 값을 가진 노드를 찾을 때 선형 탐색을 이용한다면: $O(N^2)$
그 이유는 가장 작은 노드를 찾을 때 for문이 쓰여 이 부분이 선형 탐색이라면 $O(N)$ 그 위에 시작 노드와 끝 노드를 뺀 나머지 노드를 모두 탐색해야하므로 for문이 쓰인다. 때문에 이중 for문 $O(N)$이 되어 제곱이 된다.
1. 개요
다익스트라 알고리즘(Dijkstra’s Algorithm)은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을 반복하는 것이다.
주로 인공위성 GPS 소프트웨어나 네트워크 라우팅 등에 사용된다. 보다 실생활에 밀접하게는 네비게이션의 두 도시를 잇는 가장 빠른 길을 찾는데 사용될 수 있다.
2. 특징
1개의 출발점에서 1개의 도착지까지 가는 최소 비용 경로를 알기 위해 1개의 출발점에서 모든 도착점까지 가는 최소 비용 경로를 찾는다. 원하는 도착지에 도달하면 알고리즘을 종료한다.
용어 정의
3. 경로 구하기
u에서 출발해 모든 노드로 가는 최소비용 경로를 알아보자.
이 그래프에서 노드 u로부터의 최소 비용 경로 그래프
4. 시간 복잡도
참고자료