[알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm)

Dijkstra Algorithm ?

다이나믹 프로그래밍을 활용한 최단경로 탐색(Shortest Path Search)알고리즘 입니다.

특정한 하나의 시작지점에서 다른 모든 지점으로 가는 최단 경로를 탐색 합니다.

그래프의 방향의 유무는 상관이 없으나, 간선들중 단 하나라도 가중치가 음수(-)일 경우 다익스트라 알고리즘은 사용할 수 없습니다.

그래프 내에 가중치의 합이 음인 사이클이 존재한다면 무한하게 음의 사이클을 도는 경우 경로의 합이 음수의 무한대가 되기 때문에 최단 경로를 구성할 수 없게 되기 때문입니다.

출처 : https://gfycat.com/ko/dopeyartisticfinnishspitz

 

다익스트라 알고리즘의 원리

1. 출발 노드를 설정

2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장

3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택

4. 해당 노드를 통하여 목표 노드로 가는 경우를 고려하여 최소 비용을 갱신

5. 목표 노드에 도착할때까지 3번 4번의 괴정을 반복

 

다익스트라 알고리즘의 장단점

장점

1. 그래프가 큰 경우에도 문제 없이 사용이 가능하다.

2. 모든 경우의 수를 탐색하기 때문에 정확한 최소비용을 얻을 수 있다.

 

단점

1. 음수인 가중치를 가진 간선이 있을 경우에는 사용할 수 없다.

2. 모든 경우의 수를 탐색하기 때문에 비용이 높다.

 

현재 다익스트라 알고리즘을 실제 구현하여 적용시킨 코드는 없으므로 다른 블로그의 영상 및 코드를 참고하도록 합니다.

 

 

다익스트라 참고 블로그 (영상 포함)

https://m.blog.naver.com/ndb796/221234424646

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

https://yabmoons.tistory.com/364

[ 다익스트라 알고리즘 ] 개념과 구현방법 (C++)

---

다익스트라 알고리즘(Dijkstra Algorithm) 구현하기

그래프를 참고하여 다익스트라 알고리즘을 C++ 코드로 구현하였습니다.

위의 그래프를 기준으로 노드와 간선을 설정하였습니다.

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <queue>
#include <Windows.h>

using namespace std;

class DiNode // 노드의 정보
{
public:
    string id; // 이름
    map<DiNode*, int> neighbors;  // 연결된 노드와 가중치(간선)를 저장하는 맵

    void Print() // 출력함수
    {
        cout << id;
    }
};

class Di // 다익스트라 알고리즘
{
public:
    vector<DiNode> nodes;  // 모든 노드를 저장하는 벡터

    struct PathResult
    {
        vector<DiNode> path;  // 최단 경로를 구성하는 노드들
        int distance;        // 최단 거리
    };

    // 출발 노드에서 도착 노드까지의 최단 경로와 거리를 반환하는 함수
    PathResult PathFinding(int from, int to)
    {
        // 노드의 인덱스에 따라 노드를 참조할 수 있도록 맵을 만듦
        map<int, DiNode*> nodeMap;
        for (int i = 0; i < nodes.size(); i++)
        {
            nodeMap[i] = &nodes[i];
        }

        // 출발 노드에서부터의 거리를 저장하는 배열
        vector<int> distance(nodes.size(), INT_MAX);
        distance[from] = 0;

        // 방문 여부를 저장하는 배열
        vector<bool> visited(nodes.size(), false);

        // 최단 경로를 구하기 위한 우선순위 큐
        // greater = 우선순위큐는 최대부터 반환하지만 greater를 사용하여 오름차순 즉, 최소먼저 반환하도록한다!
        priority_queue<pair<int, DiNode*>,
            vector<pair<int, DiNode*>>,
            greater<pair<int, DiNode*>>> pq;

        pq.push({ 0, nodeMap[from] }); // 우선 시작지점을 0으로 푸쉬한다.

        // 다익스트라 알고리즘 수행
        while (!pq.empty())
        {
            int currDistance = pq.top().first;
            DiNode* currNode = pq.top().second;
            pq.pop();

            // 이미 방문한 노드는 스킵
            if (visited[currNode - &nodes[0]])
                continue;

            visited[currNode - &nodes[0]] = true;

            // 인접한 노드들에 대해 최단 거리를 업데이트하고 큐에 삽입
            for (auto neighbor : currNode->neighbors)
            {
                int newDistance = currDistance + neighbor.second;
                if (newDistance < distance[neighbor.first - &nodes[0]])
                {
                    distance[neighbor.first - &nodes[0]] = newDistance;
                    pq.push({ newDistance, neighbor.first });
                }
            }
        }

        // 최단 경로를 구성하는 노드들을 저장하는 벡터 생성
        vector<DiNode> path;
        DiNode* currNode = nodeMap[to];
        path.push_back(*currNode);
        while (currNode != nodeMap[from])
        {
            for (auto neighbor : currNode->neighbors)
            {
                if (distance[currNode - &nodes[0]] - neighbor.second == distance[neighbor.first - &nodes[0]])
                {
                    currNode = neighbor.first;
                    path.push_back(*currNode);
                    break;
                }
            }
        }

        // 경로를 출발지부터 도착지까지의 순서로 뒤집음
        reverse(path.begin(), path.end());

        PathResult result;
        result.path = path;
        result.distance = distance[to];
        return result;
    }
};

int main()
{
    Di di;

    // 노드 생성
    for (char c = 'A'; c <= 'I'; c++)
    {
        DiNode node;
        node.id = string(1, c);
        di.nodes.push_back(node);
    }

    // 간선 연결 설정하기 (준비된 이미지를 참고합니다)
    //0번 A하고 연결된 간선
    di.nodes[0].neighbors[&di.nodes[1]] = 3;
    di.nodes[0].neighbors[&di.nodes[2]] = 4;
    //1번 B하고 연결된 간선
    di.nodes[1].neighbors[&di.nodes[0]] = 3;
    di.nodes[1].neighbors[&di.nodes[2]] = 4;
    di.nodes[1].neighbors[&di.nodes[3]] = 3;
    di.nodes[1].neighbors[&di.nodes[4]] = 3;
    //2번 C하고 연결된 간선
    di.nodes[2].neighbors[&di.nodes[0]] = 4;
    di.nodes[2].neighbors[&di.nodes[1]] = 4;
    di.nodes[2].neighbors[&di.nodes[3]] = 4;
    di.nodes[2].neighbors[&di.nodes[8]] = 4;
    //3번 D하고 연결된 간선
    di.nodes[3].neighbors[&di.nodes[1]] = 3;
    di.nodes[3].neighbors[&di.nodes[2]] = 4;
    di.nodes[3].neighbors[&di.nodes[4]] = 4;
    di.nodes[3].neighbors[&di.nodes[5]] = 6;
    di.nodes[3].neighbors[&di.nodes[7]] = 2;
    di.nodes[3].neighbors[&di.nodes[8]] = 5;
    //4번 E하고 연결된 간선
    di.nodes[4].neighbors[&di.nodes[1]] = 3;
    di.nodes[4].neighbors[&di.nodes[3]] = 4;
    di.nodes[4].neighbors[&di.nodes[5]] = 5;
    //5번 F하고 연결된 간선
    di.nodes[5].neighbors[&di.nodes[3]] = 6;
    di.nodes[5].neighbors[&di.nodes[4]] = 5;
    di.nodes[5].neighbors[&di.nodes[6]] = 4;
    //6번 G하고 연결된 간선
    di.nodes[6].neighbors[&di.nodes[5]] = 4;
    di.nodes[6].neighbors[&di.nodes[7]] = 3;
    //7번 H하고 연결된 간선
    di.nodes[7].neighbors[&di.nodes[3]] = 2;
    di.nodes[7].neighbors[&di.nodes[6]] = 3;
    di.nodes[7].neighbors[&di.nodes[8]] = 5;
    //8번 I하고 연결된 간선
    di.nodes[8].neighbors[&di.nodes[2]] = 4;
    di.nodes[8].neighbors[&di.nodes[3]] = 5;
    di.nodes[8].neighbors[&di.nodes[7]] = 5;

    int from, to;

    while (true)
    {
        system("cls");
        cout << "다익스트라 알고리즘(Dijkstra Algorithm)" << endl << endl;
        cout << "출발지(숫자)를 입력해주세요 (A=0, B=1, C=2, .., i=8): ";
        cin >> from;
        if (from < 0 or from > 8)
        {
            cout << "잘못 입력하였습니다. 범위는 0~8 까지 입니다." << endl;
            Sleep(1500);
            continue;
        }

        cout << "도착지(숫자)를 입력해주세요 (A=0, B=1, C=2, .., i=8): ";
        cin >> to;
        if (to < 0 or to > 8)
        {
            cout << "잘못 입력하였습니다. 범위는 0~8 까지 입니다." << endl;
            Sleep(1500);
            continue;
        }

        Di::PathResult result = di.PathFinding(from, to);
        cout << endl;

        cout << "경로 : ";
        for (int i = 0; i < result.path.size(); i++)
        {
            cout << "[Path" << i << "]";
            result.path[i].Print();
            if (i < result.path.size() - 1) cout << " -> ";
        }
        cout << endl;

        if (result.distance != 0)
            cout << "비용 : " << result.distance << endl;

        else if (result.distance == 0)
            cout << "출발지와 도착지가 같습니다. 비용 : " << result.distance << endl;
        cout << endl;

        system("Pause");
    }

    return 0;
}