다익스트라 최단 경로 알고리즘, Dijkstra shortest path algorithm

 

우선 이 알고리즘을 쓰기 위해서는 몇가지 조건이 필요하다.

1. 각 간선에 대한 가중치가 음수여선 안된다. -> 양수여야만 한다.

2. 단일 시작점에 대한 최단 경로이다. -> 해당 시작점에 대해서만 최단경로고 다른 vertex는 다시 돌려야 한다.

3. 프림의 MST 알고리즘과 유사한 형태다.

-> 프림 알고리즘은 경계로부터의 최소 거리를 정점의 거리 값으로 설정

-> 다익스트라에서는 시작 정점으로부터 각 정점까지의 전체거리 사용

-> 다익스트라에서는 목적 정점만 파악하면 종료

 

아무튼 조금 다르다.

 

우선 기본적으로 해야 할 것들을 알아보자

 

1. 모든 정점에 대해서 거리 값을 무한대로 초기화한다 -> 계산하지 않았음을 의미한다.

2. 시작정점 자기자신과의 거리는 0이므로 0으로 설정한다.

3. 모든 거리 값을 최소 힙, Min heap에 추가한다. (항상 꺼내는 노드가 최소거리를 가지고 있다는 뜻이다)

4. 최소힙에서 정점을 하나 꺼내어 시작 정점에서 가장 가까운 정점으로 계산해서 거리 값을 업데이트한다.

-> 처음엔 당연히 자기 자신이 뽑힐 것이다.

5. 만약 해당 정점이 도착 노드이면 해당 값을 반환하고 종료한다.

6. 꺼낸 정점과 인접한 정점, V에 대해 거리 값을 계산하고 만약 (V의 거리 값)이 (U까지의 거리 값 + U에서 V까지의 가중치)보다 크면 V까지 도달하는 짧은 경로를 찾은 것이다.

따라서 V의 거리 값을 U까지의 거리 값 + U에서 V까지의 가중치로 업데이트 한다.

7. 만약 방문하지 않은 정점이 남아있다면  4번 과정으로 다시 돌아간다.

 

??? 말로하면 못알아들으니 코드로 구현해보자

어떤 부분을 만들어야하는지 알아보자

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <limits>
#include <queue>
#include <algorithm>

using namespace std;

//시작 정점과 각 정점까지의 최소 거리 정보를 저장하기 위해 Label 구조체 생성
//즉, 정점에 대한 거리
template <typename T>
struct Label
{
    unsigned ID;
    T distance;
    
    //Label 객체 비교는 distance 를 이용 -> 호출한 객체가 호출된 객체보다 크면 true
    inline bool operator > (const Label<T>& l)const
    {
        return this->distance > l.distance;
    }
};

//다익스트라 알고리즘 (연결상태와 시작노드, 도착노드를 파라미터로 받음)
template <typename T>
auto dijkstra_shortest_path(const Graph<T>& G, unsigned src, unsigned dst)
{
     //최소 힙 생성
     priority_queue<Label<T>, vector<Label<T>>, greater<Label<T>>> heap;
     //greater 함수로 최소힙으로 만듬
     
     //모든 정점에 거리 값 테이블 초기화 -> distance는 거리를 저장하는 테이블임
     vector<T> distance(G.vertices(), numeric_limits<T>::max());
     
     set<unsigned> visited; //방문
     vector<unsigned> parent(G.vertices)); // 이동 경로 저장
     
     heap.emplace(Label<T>{src, 0}); //처음 시작정점부터 시작하기 위해 힙에 시작정점 넣음
     parent[src] = src;
     
     while(!heap.empty())
     {
         auto current_vertex.ID == heap.top(); //현재 거리값 최소인 노드 방문
         heap.pop();
         
         //만약 도착노드라면 종료
         if(current_vertex.ID == dst)
         {
             cout << current_vertex.ID << "도착";
             break;
         }
         
         //아니라면 계속 진행
         if(visited.find(current_vertex.ID) == visited.end())
         {
             //현재 꺼낸 정점과 연결된 인접 정점에 대해 조사
             for(auto& e : G.edges(current_vertex.ID))
             {
                 auto neighbor = e.dist;
                 auto new_distance = current_vertex.distance + e.weight;
                 
                 //만약 인접한 정점의 거리 값이 새로운 경로에 의한 거리 값보다 크면
                 //값을 업데이트 후 힙에 추가
                 if(new_distance < distance[neighbor])
                 {
                     heap.emplace(Label<T>{neighbor, new_distance);               
                     parent[neighbor] = current_vertex.ID;
                     distance[neighbor] = new_distance;
                 }
             }
             
             visited.insert(current_vertex.ID); 꺼낸 정점에 대해 방문처리
         }
     }
     
     //백트래킹처럼 시작정점부터 도착정점 도달할 때까지 경로 업데이트
     
     vector<unsigned> shortest_path;
     auto current_vertex = dst;
     
     while(current_vertex != src)
     {
         shortest_path.push_back(current_vertex);
         current_vertex = parent[current_vertex];
     }
     
     shortest+path.push_back(src);
     reverse(shortest_path.begin(), shortest_path.end());
     
     return shortest_path;
 }

 

솔직히 이건 templace을 사용해서 알다시피.. 일반화시킨 것이고

실제로 코딩테스트에는 조금 더 간단하게 구현할 수 있다.

설명도 더 간단하게 할 수 있다.

 

 

1. 힙에 (0, start)를 넣는다.

 

2. 힙에서 거리가 가장 작은 원소를 꺼낸다( Min heap으로 만들어서 top에서 꺼내자)

꺼낸 노드에 대한 거리가 최단 거리 테이블과 다르면 동작하지 않는다.

 

3. 원소가 가리키는 정점을 u라하면 u와 인접한 정점들에 대해 u를 거쳐서 도달하는 거리 값이 기존 테이블의 값보다 작다면 테이블의 값을 갱신한다. 그리고 힙에 (거리, 인접 정점 번호)를 추가한다.

 

4. 힙이 빌 때까지 2,3을 반복한다.

 

구현해보자

//.....
//위에 헤더 포함 이후


int v,e,st; //st는 시작노드 v는 vertex개수, e는 edge 개수

vector<pair<int,int>> adj[MAX]; // 인접행렬이지만 벡터로 담아 메모리 최소화

const int INF = 123456789;

int dist[MAX]; //최소 거리를 담는 테이블

//... 입력 받아야하는 것들: 연결 상태, 간선 가중치, 정점 개수, 간선 개수
//... 해야하는 것들: dist 테이블 초기화(INF로 만들기)


void Dijkstra(){
	//최소힙 생성 -> pair<int,int>에 대한 -> 첫번째 키가 최소, 같으면 두번째 키가 최소일때
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> heap;
    dist[st] = 0; //시작 노드
    
    heap.push({dist[st], st}); //(거리, 노드번호)를 넣음
    
    while(!heap.empty()){
    	//현재 값(고른 정점)은 heap에서 가장 최소인 거리의 노드
        //거리가 같은 것이 많다면 노드 번호가 작은 노드
        auto cur = heap.top();
        heap.pop();
        
        //뽑은 노드에 대해서 거리와 번호 뽑아냄
        int distance = cur.first;
        int idx = cur.second;
        
        //현재 뽑은 노드에 대해서 최소거리 테이블에 비교
        //즉, 시작점에서부터 뽑은노드까지의 거리(비용)가
        //최소거리 테이블에 저장된 값과 다르다면?
        //항상 dist테이블은 최소비용만 저장되기에
        //현재 힙에서 다른 값이 들어왔다면 다른 노드를 방문했을 때
        //힙에 넣은 것이 들어온 것이고 다시 조사할 필요는 없음.
        if(dist[idx] < dist) continue;
        //어차피 다른 곳에서 최솟값으로 갱신할 때 
        //들어온 다른 원소가 있을 것이기 때문에 괜찮다.
        //그렇다면 현재 뽑은 노드와 연결된 노드에 대해서 조사
        for(auto next : adj[idx]){
            int cost = next.first
            int nidx = next.second;
            //만약 현재 뽑은 노드를 거쳐서 해당 노드에 가는 것이
            //기존에 알고 있는 값보다 작으면 최소거리 테이블 갱신
            if(d[nidx] > dist+cost){
                dist[nidx] = dist + cost;
                //최소 거리를 갱신할 수 있게 하는 해당 노드를 힙에 넣음
                heap.push({dist[nidx], nidx});
            }
        }
    }
}

 

조금 다른 점이 있다면

목표 지점이 필요없는 것?

무조건 시작지점에 대해 모든 정점과 거리를 표현하고 싶다는 것..?

 

st에 대해서 5번까지의 최단거리를 알고싶다?

dist[5]를 알아내기만 하면 된다.

 

[문제풀이(Problem Solving)] - 백준, BOJ, 1916번, 최소비용 : C++ [CPP] ★★★