Dijkstra

그래프에서 정점끼리의 최단 경로를 구하는 알고리즘에는 다익스트라, 벨만-포드, 플로이드가 존재한다.

이번에는 다익스트라에 대해서 알아보도록 한다.

Dijkstra algorithm 다익스트라 알고리즘

• 개념 : 하나의 정점에서 다른 모든 정점들의 최단 경로를 구하는 방법
• 구현 방식 : priority queue 사용 (priority queue는 내림차순으로 정렬해줌을 주의)
• 작동 방식

첫 정점을 기준으로 연결되있는 정점들을 추가하며, 최단 거리를 갱신한다.

(거리를 저장하는 배열의 초기값은 무한대 값으로 저장한다.)

• 그림 예시 (파란색은 각 정점 사이의 가중치를 뜻한다.)

  정점이 7개 있을때의 그래프

  
  

  
  

1을 중심으로 다른 정점들까지의 최단 거리를 구한다고 하면, 거리 배열은

이런 모습으로 만들어진다.

만약, 다른 정점으로 가는 간선이 없다면 거리 배열안에는 INF 무한대의 값이 들어가 있을 것이다.

     ★ 음수 가중치에서는 다익스트라 알고리즘의 사용이 불가능하다.

---

(ex) 

정점에서 다른 정점까지 가지 못하면 INF를 출력하고, 만약 갈 수 있다면 최단 거리를 출력하는 프로그램을 만들시,

#include <stdio.h>
#include <queue>
#include <vector>
 
using namespace std;
 
int INF = 999999999;
int vn; //정점개수
vector <pair<int, int>> adj[20001]; //<연결된정점번호, 간선 가중치>
 
//거리 배열을 반환해주는 함수
vector <int> Dijkstra(int start) {
    //정점 start에서 다른 정점까지의 최단 거리 저장
    //****초기값은 최대한 무한값으로 설정함을주의***
    vector <int> dist(vn + 1, INF);
 
    dist[start] = 0;//시작점은 거리를 0으로 초기화
 
    priority_queue <pair<int, int>> qu; //<정점까지 거리,정점> ,내림차순 정렬
    qu.push({ 0,start });
    
    while (!qu.empty())
    {
        int cost = -qu.top().first; //qu에다 push할때 음수로 push했으니깐 -붙여주기 (priority queue가 내림차순이라)
        int here = qu.top().second;
        qu.pop();
        if (cost > dist[here]) continue; //만약 꺼낸 거리가 이미 갱신된 거리보다 길 경우 패스
 
        for (int i = 0; i < adj[here].size(); i++) {
            int next = adj[here][i].first;
            int nextdist = adj[here][i].second + cost;
            if (dist[next] > nextdist) {
                dist[next] = nextdist;
                qu.push({ -nextdist, next });//거리의 부호를 바꾸어 거리가 작은 정점부터 꺼내지도록하기 위해
            }
 
        }
        
    }
    return dist;
}
 
int main() {
    int en,start; // 간선 개수, 시작점
    scanf("%d %d", &vn, &en);
    scanf("%d", &start);
    
    for (int i = 0; i < en; i++) {
        int first, second, cost;//cost는 10 이하의 자연수
        scanf("%d %d %d", &first, &second, &cost);
        adj[first].push_back(make_pair(second, cost));
    }
 
    vector <int> check; //start 정점에서 다른 정점까지의 거리를 저장
    check = Dijkstra(start);
    for (int i = 1; i < check.size(); i++) {
        if (check[i] == INF) {
            printf("INF\n");        
        }
        else {
            printf("%d\n", check[i]);
        }
    }
    return 0;
}