[자료 구조] 최단 경로 - 다익스트라(Dijkstra) 알고리즘 개념 및 구현 *

1. 최단 경로

- 최단 경로 문제는 정점 i와 j를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다.

- 최단 경로를 찾는 대표적인 알고리즘으로 다익스트라, 플로이드 워셜, 벨만포드가 있다.

 

2. 최단 경로 알고리즘

1) 다익스트라(Dijkstra)

① 개념 : 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘이다.

※ 조건 : 음수 가중치와 음수 사이클은 없다고 가정한다.

 

② 동작 과정

- 시작점으로부터 가장 가까운 정점을 방문

- 방문한 정점에서 인접한 정점들에 대해 거리를 갱신

 

위와 같은 그래프가 있을 때, v0을 시작노드라고 하면 아래와 같이 거리가 갱신된다.

v0	v1	v2	v3	v4	v5
0	50	10	INF	45	INF

 

그다음 노드를 v2라고 하면  v2에 인접한 정점들에 대해 거리를 갱신한다.

v0	v1	v2	v3	v4	v5
0	50	10	10+15 = 25	45	INF

 

그다음 노드를 v3이라고 하고 거리를 갱신한다.

 

v0	v1	v2	v3	v4	v5
0	50 => 45	10	25	45	INF

그다음 노드를 v1이라고 하고 거리를 갱신한다.

v0	v1	v2	v3	v4	v5
0	45	10	25	45	INF

 

마지막으로 v4와 v5에 대해 갱신해 준다. (v5는 갈 수있는 노드가 없어서 INF가 된다.)

v0	v1	v2	v3	v4	v5
0	45	10	25	45	INF

 

 

③ 구현 방법

- 시작 정점에서 다른 정점으로 가는 최단거리를 기록하는 배열이 필요하다 = distance[]

- 시작 정점을 v이라 하면, distance[v] = 0이고 다른 정점에 대한 distance 값은 시작정점과 해당정점간의 가중치값 

- 가중치를 저장하는 배열은 wight이라고 한다. => v~w까지의 가중치는 weight[v][w]

 

- 시간 복잡도 : 정점을 방문할 때마다 갱신하는 과정을 매번 해야하므로 인접행렬을 이용하면 O(n^2)이.,

                    힙(우선순위 큐)을 이용하면 O(logV)에 구현이 가능하다. 

* 우선순위 큐 : 원소에 우선순위(오름차순, 내림차순)이 존재하고 우선순위가 높은 원소부터 출력함

≫ 최대값과 최소값을 O(logN)만에 찾을 수 있다.

 

 

1753번: 최단경로 (acmicpc.net)

1753번: 최단경로

 

👉 인접 행렬을 이용한 O(n^2) 구현

##

 

👉 우선순위 큐를 이용한 O(logV) 구현

#include <iostream>
#include <algorithm> 
#include <queue>
using namespace std;

#define INF 99999999
int v, e, k;
vector<pair<int, int>> graph[20001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(nullptr);

    cin >> v >> e >> k;

    int x, y, w;
    for (int i = 0; i < e; i++) {
        cin >> x >> y >> w;
        graph[x].push_back(make_pair(y, w));
    }


    vector<int> dist(v + 1, INF);
    priority_queue<pair<int, int>> pq;
    dist[k] = 0;
    pq.push(make_pair(0, k));

    while (!pq.empty()) {
        pair<int, int> cur = pq.top();
        //우선순위 큐는 내림차순이기 때문에 최단경로를 구하기 위해선 앞에 -를 붙인다.
        int cost = -cur.first; //가중치
        int here = cur.second; //다음번 원소
        pq.pop();

        if (cost > dist[here]) continue;

        for (int i = 0; i < graph[here].size(); i++) {
            int next = graph[here][i].first;
            int nextcost = graph[here][i].second;
            if (dist[next] > nextcost + cost ){
                dist[next] = nextcost + cost;
                pq.push(make_pair(-dist[next], next));
            }
        }
    }

    for (int i = 1; i < v + 1; i++)
    {
        if (dist[i] == INF)
            cout << "INF" << '\n';
        else
            cout << dist[i] << '\n';
    }
    return 0;
}