본문 바로가기

알고리즘/그래프 순회(GraphTraversal)

[알고리즘] 최단 경로 탐색(데이크스트라 알고리즘) - 코딩밥상

데이크스트라(Dijkstra) 알고리즘이란?

최단 경로 탐색이란 그래프 내의 한 정점에서 다른 정점으로 이동할 때 가중치 합이 최솟값인 경로를 찾는 알고리즘입니다.

그 중 대표적인 알고리즘으로 데이크스트라 알고리즘이 있습니다. 이는 프림 알고리즘과 동작 방식이 상당히 비슷합니다. 다만 프림 알고리즘이 단순히 간선의 길이를 이용하여 어떤 간선을 먼저 연결할지 결정하는 데 비해 데이크스트라 알고리즘은 경로의 길이를 감안해서 간선을 연결한다는 점이 다릅니다. 또 다른 중요한 차이점은 데이크스트라 알고리즘의 경우 사이클이 없는 방향성 그래프에 한해서만 사용할 수 있다는 것입니다.

 

간단하게 데이크스트라 알고리즘에대해 정리하자면,

  1. 각 정점에는 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 준비하고 각 정점에 대한 경로의 길이를 무한대로 초기화합니다.
  2. 시작 정점의 경로의 길이를 0으로 초기화하고 최단 경로에 추가합니다.
  3. 최단 경로에 새로 추가된 정점의 인접 정점에 대해 경로 길이를 갱신하고 이들을 최단 경로에 추가합니다. 만약 추가하려는 인접 정점이 이미 최단 경로 안에 있다면, 갱신되기 이전의 경로 길이가 새로운 경로 길이보더 더 큰 경우에 한해 다른 선행 정점을 지나던 기존 경로가 현재 정점을 경유하도록 수정합니다.
  4. 그래프 내의 모든 정점이 최단 경로에 소속될 때까지 과정을 반복하고 종료합니다.

구현

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));
            }
        }
    }
}