다익스트라 (Dijkstra)

August 11, 2023

카테고리: A&D

다익스트라 (Dijkstra)

다익스트라: 한 점에서 다른 점까지의 최단경로를 파악하는 최단경로 탐색 알고리즘

작동과정

출발 노드와 연결된 노드의 거리를 저장하고 연결되지 않은 노드와의 거리는 최댓값 INF로 설정.
연결된 노드 중 방문하지 않고 가장 거리가 적은 노드를 방문.
해당 노드를 거쳐 다른 노드를 방문하는 경우를 계산하여 거리가 더 적다면 갱신.
모든 노드에 대해 반복.

위의 과정을 모든 노드에 대해 반복하면 출발 노드에서 다른 모든 노드까지의 최소 거리 배열을 구할 수 있다.

방문하지 않은 노드 중 거리가 가장 작은 노드를 구하는 방법은 두가지가 있다.

방문여부를 기록한 배열을 만들어 거리가 가장 작은 노드를 구한다.
우선 순위 큐를 통해 가장 적은 거리로 연결된 노드를 가져온다.

1번의 경우 노드들을 계속하여 탐색하기 때문에 최소 시간 복잡도가 O(N^2), 2번의 경우 힙 구조를 사용하기 때문에 O(NlogN)이 나온다.

//1번
#include<vector>
using namespace std;

#define INF 1000000

class Dijkstra
{
public:
    Dijkstra(int nodeCount)
        : nodeCount(nodeCount)
    {
        ad.assign(nodeCount, vector<int>());
        selected.assign(nodeCount, false);
        dist.assign(nodeCount, INF);
    }

    // 간선 연결
    void MakeEdge(int start, int weight)
    {
        ad[start].push_back(weight);
    }


    // 현재 방문하지 않은 노드 중에서 가장 거리가 짧은 노드의 인덱스 반환
    int GetSmallIndex()
    {
        int minDist = INF;
        int index = 0;

        for (int i = 0; i < nodeCount; i++)
        {
            if (dist[i] < minDist && selected[i] == false) {
                minDist = dist[i];
                index = 0;
            }
        }
    }

    // start 노드를 기준으로 각 노드로 향하는 최소 비용을 계산
    void FindPath(int start)
    {
        // 초기 dist값을 선택한 start 지점의 가중치 값으로 세팅한다.
        for (int i = 0; i < nodeCount; i++)
            dist[i] = ad[start][i];


        // start 노드 방문 체크
        selected[start] = true;

        //반복

        for (int i = 0; i < nodeCount - 2; i++)
        {
        // 방문하지 않은 노드중 현재 가장 가까운 노드의 인덱스를 구한다.
            int current = GetSmallIndex();

        // 선택된 노드 방문 체크
            selected[current] = true;

        // 선택된 노드를 기준으로 방문하지 않은 노드로 가는 경우의 비용을 계산해
            for (int j = 0; j < nodeCount; j++)
            {
                if (selected[j] == false)
                {
                    // 만약 이전의 최소 비용보다 적다면 갱신해준다.
                    if (dist[j] > dist[current] + ad[current][j])
                        dist[j] = dist[current] + ad[current][j];
                }
            }
        }

    }

private:
    // 간선 저장
    vector<vector<int>> ad;

    // 노드 방문 여부
    vector<bool> selected;

    // 해당 노드로 가는 최소 비용을 저장하는 배열
    vector<int> dist;

    // 노드 개수 저장
    int nodeCount = 0;
};

// 2번
#include <queue>

// <가중치, 향하는 노드>
typedef pair<int, int> PII;

class Dijkstra2
{
public:
    Dijkstra2(int nodeCount)
        : nodeCount(nodeCount)
    {
        ad.assign(nodeCount, vector<PII>());
        dist.assign(nodeCount, INF);

    }

    void MakeEdge(int node, int next, int weight)
    {
        ad[node].push_back(PII(weight, next));
    }

    void FindPath(int start)
    {

        priority_queue<PII, vector<PII>, greater<PII>> pq;
        pq.push(PII(0, start));

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

            if (dist[current] < distance) continue;

            for (int i = 0; i < ad[current].size(); i++)
            {
                int next = ad[current][i].second;

                int nextDist = distance + ad[current][i].first;

                if (nextDist < dist[next])
                {
                    dist[next] = nextDist;
                    pq.push(PII(nextDist, next));
                }
            }

        }
    }

private:
    vector<vector<PII>> ad; // 해당 노드랑 연결된 간선 저장
    vector<int> dist; // 가중치 저장
    int nodeCount = 0; // 노드 개수 저장
};

평생하는 개발 공부

다익스트라 (Dijkstra)