데이크스트라(Dijkstra) 알고리즘이란?
최단 경로 탐색이란 그래프 내의 한 정점에서 다른 정점으로 이동할 때 가중치 합이 최솟값인 경로를 찾는 알고리즘입니다.
그 중 대표적인 알고리즘으로 데이크스트라 알고리즘이 있습니다. 이는 프림 알고리즘과 동작 방식이 상당히 비슷합니다. 다만 프림 알고리즘이 단순히 간선의 길이를 이용하여 어떤 간선을 먼저 연결할지 결정하는 데 비해 데이크스트라 알고리즘은 경로의 길이를 감안해서 간선을 연결한다는 점이 다릅니다. 또 다른 중요한 차이점은 데이크스트라 알고리즘의 경우 사이클이 없는 방향성 그래프에 한해서만 사용할 수 있다는 것입니다.
간단하게 데이크스트라 알고리즘에대해 정리하자면,
- 각 정점에는 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 준비하고 각 정점에 대한 경로의 길이를 무한대로 초기화합니다.
- 시작 정점의 경로의 길이를 0으로 초기화하고 최단 경로에 추가합니다.
- 최단 경로에 새로 추가된 정점의 인접 정점에 대해 경로 길이를 갱신하고 이들을 최단 경로에 추가합니다. 만약 추가하려는 인접 정점이 이미 최단 경로 안에 있다면, 갱신되기 이전의 경로 길이가 새로운 경로 길이보더 더 큰 경우에 한해 다른 선행 정점을 지나던 기존 경로가 현재 정점을 경유하도록 수정합니다.
- 그래프 내의 모든 정점이 최단 경로에 소속될 때까지 과정을 반복하고 종료합니다.
구현
void Dijkstra()
{
priority_queue<pair<int, int>> PQ; //우선순위 힙 사용
PQ.push(make_pair(0, Start)); //시작 노드 설정
Distant[Start] = 0;
while (!PQ.empty()){
int PathCost = PQ.top().first;
int Current = PQ.top().second;
PQ.pop();
for (int i = 0; i < Vertex[Current].size(); i++) //인접 노드 체크
{
int Next = Vertex[Currnet][i].first;
int NextCost = Vertex[Current][i].second;
if (Distant[Next] > PathCost + NextCost){ //기존 경로값 보다 작으면 갱신
Distant[Next] = PathCost + NextCost;
PQ.push(make_pair(Distant[Next], Next));
}
}
}
}
'알고리즘 > 그래프 순회(GraphTraversal)' 카테고리의 다른 글
[알고리즘] 최소 신장 트리 알고리즘(Minimum Spanning Tree Algorithm) - 코딩밥상 (0) | 2023.01.22 |
---|---|
[알고리즘] 위상 정렬(Topological Sort) - 코딩밥상 (0) | 2023.01.19 |
[알고리즘] BFS(넓이 우선 탐색) - 코딩밥상 (0) | 2023.01.18 |
[알고리즘] DFS(깊이 우선 탐색) - 코딩 밥상 (0) | 2023.01.18 |