1. 다익스트라 알고리즘
- 특정 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산
- 음의 간선이 없을 때 정상적으로 동작
- 현실 세계의 도로(간선)는 음의 간선으로 표현되지 않는다.
- 그리디 알고리즘으로 분류된다.
- 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복
- 단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않는다.
- 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해 가능
2. 동작 과정
1) 출발 노드를 설정한다.
2) 최단 거리 테이블을 초기화한다. (다른 노드로 가는 거리를 무한으로 설정. 자기 자신은 0)
3) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
5) 위 과정에서 3)과 4)를 반복한다.
6) 알고리즘이 끝나고 나면 최단 거리 테이블에 각 노드까지의 최단 거리 정보가 저장된다.
3. 동작 예시
1) 최단 거리 테이블에서 출발 노드 자신에 대해서는 0, 다른 노드들에 대해서는 무한으로 초기화
2) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드는 1번이므로 1번 노드를 거쳐갈 때 인접 노드들의 최단 거리 테이블을 갱신한다. (기존 값보다 작은 값일 때)
- 2번 노드 : 1번 노드까지 최단 거리 0 + 1번 노드 ~ 2번 노드까지의 거리 2 = 2 (< 무한)
- 3번 노드 : 1번 노드까지 최단 거리 0 + 1번 노드 ~ 3번 노드까지의 거리 5 = 5 (< 무한)
- 4번 노드 : 1번 노드까지 최단 거리 0 + 1번 노드 ~ 4번 노드까지의 거리 1 = 1 (< 무한)
3) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드는 4번이므로 4번 노드를 거쳐갈 때 인접 노드들의 최단 거리 테이블을 갱신한다. (기존 값보다 작은 값일 때)
- 3번 노드 : 4번 노드까지 최단 거리 1 + 4번 노드 ~ 3번 노드까지의 거리 3 = 4 (< 5)
- 5번 노드 : 4번 노드까지 최단 거리 1 + 4번 노드 ~ 5번 노드까지의 거리 1 = 2 (< 무한)
4) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드는 2번이므로 2번 노드를 거쳐갈 때 인접 노드들의 최단 거리 테이블을 갱신한다. (기존 값보다 작은 값일 때)
- 3번 노드 : 2번 노드까지 최단 거리 2 + 2번 노드 ~ 3번 노드까지의 거리 3 = 5 (> 4)
- 4번 노드 : 2번 노드까지 최단 거리 2 + 2번 노드 ~ 4번 노드까지의 거리 2 = 4 (> 1)
=> 4번 노드는 이미 방문 처리 된 노드여서 값이 확정되었으므로 이 같은 경우에는 더이상 확인하지 않아도 된다.
5) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드는 5번이므로 5번 노드를 거쳐갈 때 인접 노드들의 최단 거리 테이블을 갱신한다. (기존 값보다 작은 값일 때)
- 3번 노드 : 5번 노드까지 최단 거리 2 + 5번 노드 ~ 3번 노드까지의 거리 1 = 3 (< 4)
- 6번 노드 : 5번 노드까지 최단 거리 2 + 5번 노드 ~ 6번 노드까지의 거리 2 = 4 (< 무한)
6) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드는 3번이므로 3번 노드를 거쳐갈 때 인접 노드들의 최단 거리 테이블을 갱신한다. (기존 값보다 작은 값일 때)
- 2번 노드 : 3번 노드까지 최단 거리 3 + 3번 노드 ~ 2번 노드까지의 거리 3 = 6 (> 2)
- 6번 노드 : 3번 노드까지 최단 거리 3 + 3번 노드 ~ 6번 노드까지의 거리 5 = 8 (> 4)
7) 마지막까지 남은 노드 6에 대해서는 처리하지 않아도 된다.
4. 우선순위 큐를 이용한 동작 과정
1) 출발 노드를 설정한다.
2) 최단 거리 테이블을 초기화한다. (다른 노드로 가는 거리를 무한대로 설정. 자기 자신은 0)
3) 우선순위 큐를 생성하고 출발 노드를 우선순위 큐에 넣는다. (거리 기준 오름차순 정렬)
4) 우선순위 큐의 가장 위에 있는 노드를 꺼내고, 해당 노드가 방문하지 않은 노드라면 그 노드의 인접 노드들까지의 거리를 기존 최단 거리 테이블과 비교한다.
5) 기존 최단 거리보다 짧으면 갱신한 뒤 해당 노드들을 우선순위 큐에 넣는다.
5) 위 과정에서 4)와 5)를 반복한다.
6) 알고리즘이 끝나고 나면 최단 거리 테이블에 각 노드까지의 최단 거리 정보가 저장된다.
5. 코드 예시
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
int n, m, start; // 노드의 개수, 간선의 개수, 시작 노드 번호
vector<vector<pii>> graph; // 그래프 데이터 저장
int d[100001]; // 최단 거리 테이블
const long long INF = 1e9; // 무한을 의미하는 값
void dijkstra(int start)
{
priority_queue<pii, vector<pii>, greater<pii>> pq; // priority_queue는 최대힙으로 구현되어 있으므로, 최소힙으로 작동하기 위해 greater 추가
pq.push(pii(0, start));
d[start] = 0;
while (!pq.empty())
{
// 가장 최단거리가 짧은 노드에 대한 정보 꺼내기
int dist = pq.top().first; // 현재 노드까지의 비용
int cur = pq.top().second; // 현재 노드 번호
pq.pop();
// 현재 노드가 이미 처리된 적이 있는 노드라면 무시
if (d[cur] < dist) continue;
// 현재 노드와 연결된 다른 인접 노드들을 확인
for (int i = 0; i < graph[cur].size(); i++)
{
pii curEdge = graph[cur][i];
int cost = dist + curEdge.second;
// 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if (cost < d[curEdge.first])
{
d[curEdge.first] = cost;
pq.push(pii(cost, curEdge.first));
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> start;
graph.resize(n + 1);
// 간선 정보 입력 받기
for (int i = 0; i < m; i++)
{
int a, b, c;
cin >> a >> b >> c;
graph[a].push_back(pii(b, c)); // a 노드에서 b 노드로 가는 비용이 c라는 의미
}
// 최단거리 테이블을 모두 무한으로 초기화
fill(d, d + 100001, INF);
// 다익스트라 알고리즘 수행
dijkstra(start);
// 모든 노드로 가기 위한 최단 거리를 출력
for (int i = 1; i <= n + 1; i++)
{
if (d[i] == INF)
cout << "INFINITY" << endl;
else
cout << d[i] << endl;
}
}6. 시간복잡도
- 힙 자료구조 이용하는 다익스트라 알고리즘의 시간 복잡도는 O(ElogV)
- 노드를 하나씩 꺼내 검사하는 반복문은 노드의 개수 V 이상 횟수로는 처리되지 않는다.
- 결과적으로 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 최대 간선 개수(E)만큼 연산이 수행될 수 있다.
- 직관적으로 전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 유사하다.
- 시간 복잡도를 O(ElogE)로 판단할 수 있다.
- 중복 간선을 포함하지 않는 경우 이를 O(ElogV)로 정리할 수 있다.
- O(ElogE) -> O(ElogV^2) -> O(2ElogV) -> O(ElogV)
👁️🗨️ 참고
https://www.youtube.com/watch?v=acqm9mM1P6o&t=514s (동빈나 채널)
