Typing diary
다익스트라(Dijkstra) 알고리즘 본문
다익스트라
DP에 기반한 최단 경로 탐색 알고리즘
알고리즘 수행 결과로 최단 경로트리를 반환한다.
아이디어
힙 자료구조를 이용하여 출발 노드에서 부터 해당 노드까지 비용이 적은 순으로 경로를 탐색한다.
다음과 같은 그래프가 있다고 하자.
다익스트라 알고리즘으로 해당 그래프를 탐색하게 되면
출발 노드부터 해당 노드까지 비용이 적은순 (1 → 4 → 2 → 5 → 3 → 6)으로 탐색을 하게 된다.
해당 과정을 구현하기 위해선 현재 탐색 가능한 노드 중 비용이 가장 적은 노드가 무엇인지 알아야 한다.
(이때, 현재 탐색 가능한 노드란, 방문 했던 노드와 인접한 노드를 뜻한다.)
이를 위해 힙 자료구조를 사용하게 된다.
.
이게 무슨 소리냐...
1번 노드를 시작 노드로, 6번 노드를 도착 노드로 정하자.
1번 노드가 시작 노드이기 때문에 1번 노드를 첫 방문 노드로 정하게 된다.
이때, 다음 탐색 가능한 노드는 현재 방문 노드인 1번 노드와 인접한 2,4번 노드이다.
2,4번 노드 중 비용이 더 낮은 노드는 4번 노드이기 때문에 다음 방문 노드로 4번 노드를 정한다.
현재 방문 노드가 4번 노드일때,
다음으로 탐색 가능한 노드는 4번 노드와 인접한 3,5번 노드가 추가되어 2,3,5번 노드가 된다.
(탐색 가능한 노드에서 방문했던 노드는 제외되기 때문에 1번 노드는 포함될 수 없다.)
2,3,5번 노드 중 출발 노드로 부터 비용이 가장 적은 노드는 2번 노드이기 때문에 다음 방문 노드로 2번 노드를 정하게 된다.
다음 과정을 도착 노드(6번 노드)에 방문할 때 까지 반복하여 탐색을 진행한다.
이 과정을 쉽게 구현하기 위해서,
방문 했던 노드들의 인접 노드를 기록하고, 그 중 비용이 가장 작은 노드를 찾을 수 있는 힙이 사용되는 것이다.
또한, 탐색 과정에서 최단 비용으로 지나온 경로를 기록하여 최단 경로 트리를 완성하게 된다.
만약 현재 방문 노드가 B이고 A → B 경로가 현재 파악된 최소 경로일때,
A → B 경로보다 A → C → B경로의 비용이 더 낮은 경우에는 어떻게 처리해야 할까?
결론부터 말하자면 해당 상황은 발생할 수 없다.
현재 방문 노드가 B라는 소리는 A → B의 비용이 A → C 또는 A → C → B의 비용보다 낮다는 것을 의미한다.
즉, 현재 방문 노드가 B라면 출발 노드에서 B까지 최소 경로는 보장된 상태이기 때문에 위 사진과 같은 상황은 발생할 수 없다.
구현
그래프
다음과 같이 그래프가 구현되어 있다고 하자.
struct Edge
{
int idx;
int dist;
};
vector<Edge> graph[NODE_NUM];
필요 변수
bool visited[NODE_NUM] //노드 중복 방문을 피하기 위한 방문 체크 변수
int costToThisNode[NODE_NUM] //출발 노드에서 해당 노드까지 최소비용을 저장할 노드
priority_queue<Edge> pq //출발 노드에서 해당 노드까지 비용을 기준으로 오름차순 정렬 된 우선순위 큐
int shortestPathTree[NODE_NUM] //모든 노드에서 출발 노드까지 최단 경로를 나타내는 Sub Tree
코드
초기화
memset(visited, false, sizeof(visited));
fill(costToThisNode, costToThisNode + MAX_NUM, INT_MAX); //비용의 최소 값을 비교해야 하기 때문에 int의 최대값으로 배열을 초기화 한다.
shortestPathTree[start] = start; //시작 노드의 경로는 자기 자신으로 돌아온다.
costToThisNode[start] = 0; //시작 노드에서 시작 노드로 가능 비용은 0이다.
pq.push({ start,0 }); //pq에 시작 노드를 push한다.
로직
while (!pq.empty()) //pq가 비어있다는 뜻은 더이상 탐색할 노드가 없다는 의미이다.
{
int curNode = pq.top().idx;
int dist = costToThisNode[curNode];
pq.pop();
if (curNode == target) //목표 노드에 도착하면 종료한다.
{
return;
}
visited[curNode] = true; //노드 방문에 대해 기록한다.
//현재 노드의 인접 노드들에 대해 반복문 수행
for (int i = 0; i < graph[curNode].size(); i++)
{
Edge closetNode = graph[curNode][i];
if (visited[closetNode.idx] == false) //이미 방문한 노드가 아니라면
{
if (costToThisNode[closetNode.idx] > dist + closetNode.dist) //현재 경로의 비용이 더 낮다면
{
//비용과 경로를 갱신한다.
costToThisNode[closetNode.idx] = dist + closetNode.dist;
shortestPathTree[closetNode.idx] = curNode;
}
pq.push({ closetNode.idx,closetNode.dist + dist });
}
}
}
전체 코드
struct Edge
{
int idx;
int dist;
};
struct compare
{
bool operator()(const Edge& a, const Edge& b)
{
return a.dist > b.dist;
}
};
vector<Edge> graph[MAX_NUM];
int shortestPathTree[MAX_NUM];
int costToThisNode[MAX_NUM]; //시작 노드에서 다른 노드 까지의 비용 최소값
bool visited[MAX_NUM];
void Dijsktra(int start, int target)
{
priority_queue<Edge, vector<Edge>, compare> pq;
memset(visited, false, sizeof(visited));
fill(costToThisNode, costToThisNode + MAX_NUM, INT_MAX);
shortestPathTree[start] = start;
costToThisNode[start] = 0;
pq.push({ start,0 });
while (!pq.empty())
{
int curNode = pq.top().idx;
int dist = costToThisNode[curNode];
pq.pop();
if (curNode == target)
{
return;
}
visited[curNode] = true;
//현재 노드의 인접 노드들에 대해
for (int i = 0; i < graph[curNode].size(); i++)
{
Edge closetNode = graph[curNode][i];
if (visited[closetNode.idx] == false)
{
if (costToThisNode[closetNode.idx] > dist + closetNode.dist)
{
costToThisNode[closetNode.idx] = dist + closetNode.dist;
shortestPathTree[closetNode.idx] = curNode;
}
pq.push({ closetNode.idx,closetNode.dist + dist });
}
}
}
return;
}