[알고리즘] 최단 경로 알고리즘 다익스트라(Dijkstra) 알아보기

최단 경로 알고리즘

최단 경로 알고리즘이란 가중치가 주어진 그래프에서 두 노드의 경로중 간선의 가중치의 합이 최소가 되는 경로를 찾는 알고리즘이다.

 

다익스트라 : 특정 한 노드에서 모든 노드 까지의 최단거리(음수 x)벨만-포드 : 다익스트라의 음의 가중치가 사이클을 형성해 무한히 작아지는걸 보안하기 위해 나옴플로이드-위셜 : 모든 노드간 최단거리

🦝 다익스트라

특정 한 노드에서 모든 노드 까지의 최단 거리를 구하는 알고리즘이다. (간선의 가중치가 음수이면 안된다는 조건이 있다.)

방문 하지 않은 경로중 가중치가 최소인 노드를 선택해 거리를 확정 해 나가는 형식이다.

 

0. Dist 의 값을 INF로 초기화 시켜준다.

1. 방문한 노드와 연결 된 노드의 Dist를 비교해 업데이트를 시켜주고, 현재 방문 노드를 방문 체크 해준다.

2. 방문한 노드와 연결 되어있는 노드중 Dist가 작은 값을 가지는 정점을 선택하고, 방문한다. 

3. 1, 2번 반복한다.

 

다음과 같은 그래프를 예시로 보이겠다. (시작 노드 = 1)

시작 노드를 노드1로 1번을 수행한 결과이다.

\

2번 수행 후 1번을 수행한 결과이다.

방문 노드와 연결 되어있는 노드중 Dist가 작은 값을 선택해 방문 한다. 그 후 Dist를 업데이트 해준다.

반복 해준다.

구현

다익스트라 구현엔 2가지 방법이 있다.

순차 탐색을 이용해 연결된 노드중 최소 Dist를 가지는 노드 찾는법[O(N^2)] 과 

최소 힙(우선순위 큐) 를 이용한 방법[O(E * logN)] 이 있다. 

나는 최적화 된 후자를 구현 하겠다.

 

#include<iostream>
#include<vector>
#include<queue>

vector<pair<int, int> > graph[100001]; //graph[u] = {v, w}  u, v = 노드, w = 가중치
int dist[100001]; // 최단 거리 테이블 만들기

void dijkstra(int start)
{
    priority_queue<pair<int,int>>pq; // 거리, 노드
    
    pq.push({0,start}); // 시작 노드 거리 = 0 
    dist[start]=0;
    
    while(!pq.empty())
    {
        int cost = -pq.top().first; //현재 노드까지의 비용
        int now = pq.top().second; // 현재 노드
        pq.pop();
        
        if(dist[now] < cost) // 이미 방문한 노드
            continue;
        
        for(int i=0; i < graph[now].size(); i++)
        {
            int next_cost = cost + graph[now][i].second; // 다음 노드의 비용을 계산
            
            if(cost<dist[graph[now][i].first]) // 비용이 더 작다면 최단경로 테이블 값 업데이트
            {
                dist[graph[now][i].first] = next_cost;
                pq.push(make_pair(-next_cost, graph[now][i].first));
            }
        }
    }
}