[c++] 다익스트라 알고리즘

 

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

using namespace std;

int number = 6;
int INF = 1000000000;

vector<pair<int, int>> a[7];
int d[7];

void init()
{
    for (int i = 1; i <= number; i++)
        d[i] = INF;

    a[1].push_back({2, 2});
    a[1].push_back({3, 5});
    a[1].push_back({4, 1});

    a[2].push_back({1, 2});
    a[2].push_back({3, 3});
    a[2].push_back({4, 2});

    a[3].push_back({1, 5});
    a[3].push_back({2, 3});
    a[3].push_back({4, 3});
    a[3].push_back({5, 1});
    a[3].push_back({6, 5});

    a[4].push_back({1, 1});
    a[4].push_back({2, 2});
    a[4].push_back({3, 3});
    a[4].push_back({5, 1});

    a[5].push_back({3, 1});
    a[5].push_back({4, 1});
    a[5].push_back({6, 2});

    a[6].push_back({3, 5});
    a[6].push_back({5, 2});
}

struct compare
{
    bool operator()(pair<int, int> a, pair<int, int> b)
    {
        return a.second < b.second;
    }
};

void dijkstra(int start)
{
    d[start] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, compare> pq;
    pq.push({start, 0});

    while (!pq.empty())
    {
        int current = pq.top().first;
        int distance = pq.top().second;
        pq.pop();

        if (d[current] < distance)
            continue;
        for (auto node : a[current])
        {
            int next = node.first;
            int nextDistance = distance + node.second;
            if (d[next] > nextDistance)
            {
                d[next] = nextDistance;
                pq.push({next, nextDistance});
            }
        }
    }
}

void printDistance()
{
    for (int i = 0; i < number; i++)
        printf("%d ", d[i]);
}

int main(void)
{
    init();
    dijkstra(1);
    printDistance();
    return 0;
}

 

코드 참고 : https://blog.naver.com/ndb796/221234424646​

23. 다익스트라(Dijkstra) 알고리즘