다익스트라

기능 : 출발 노드와 모든 노드간의 최단 거리 탐색

특징 : 에지는 모두 양수

시간 복잡도 : O(ElogV) - V는 노드 수, E는 에지 수

 

1. 인접 리스트로 그래프 구현하기

배열의 자료형은 (노드, 가중치)로 선언

 

2. 최단 거리 배열 초기화하기

출발 노드는 0, 이외의 노드를 무한으로 초기화

fill 함수는 O(N)이라서 무겁다..

memset을 사용하자

0x3f, 0x7f (제한이 더 크다면)

보통은 0x3f

 

3. 값이 가장 작은 노드 고르기

최단 거리 배열에서 현재 값이 가장 작은 노드를 고름

 

4. 최단 거리 배열 업데이트하기

선택된 노드에 연결된 에지의 값으로 다른 노드의 값을 업데이트.

"선택 노드"의 최단 거리 배열의 값 + 에지 가중치

"연결 노드"의 최단 거리 배열의 값

中 최소값

 

5. 3, 4 과정을 반복해 최단 거리 배열을 완성

4에서 선택 노드가 될 때 다시 선택되지 않도록 '방문 배열'을 만들어 처리

모든 노드가 선택되면 최단 거리 배열 완성

 

다익스트라 알고리즘은 출발 노드와 도착 노드의 간의

최단거리를 구하는 알고리즘이 아니다.

출발 노드와 이외의 모든 노드 간의 최단 거리이다.

 

https://www.acmicpc.net/problem/1753

1753번: 최단경로

우선순위 큐는 priority_queue<자료형, 구현체, 비교 연산자>로 정의

 

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
 
using namespace std;
 
typedef pair<int, int> edge;
 
// 그래프 정보 저장 인접 리스트
vector<vector<edge>> mlist;
// 최단 거리 저장 배열
vector<int> mdistance;
// 방문 배열
vector<bool> visited;
 
// greater을 해야 최소값 힙, 오름차순 정렬
//priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
priority_queue <edge, vector<edge>, greater<edge>> q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int v, e, k;
    cin >> v >> e >> k;
    mdistance.resize(v + 1);
    fill(mdistance.begin(), mdistance.end(), INT_MAX);
    visited.resize(v + 1);
    fill(visited.begin(), visited.end(), false);
    mlist.resize(v + 1);
 
    for (int i = 0; i < e; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        mlist[u].push_back(make_pair(v, w));
    }
    q.push(make_pair(0, k));
    mdistance[k] = 0;
 
    while (!q.empty())
    {
        edge current = q.top();
        q.pop();
        int c_v = current.second;
        if (visited[c_v])
            continue;
        visited[c_v] = true;
 
        for (int i = 0; i < mlist[c_v].size(); i++)
        {
            edge tmp = mlist[c_v][i];
            int next = tmp.first;
            int value = tmp.second;
 
            if (mdistance[next] > mdistance[c_v] + value)
            {
                mdistance[next] = value + mdistance[c_v];
                q.push(make_pair(mdistance[next], next));
            }
        }
    }
 
    for (int i = 1; i <= v; i++)
    {
        if (visited[i])
            cout << mdistance[i] << '\n';
        else
            cout << "INF" << '\n';
    }
    return 0;
}