다익스트라

다익스트라 알고리즘 개요

다익스트라 알고리즘은 가중치가 양수인 그래프에서 최단 경로를 찾기 위한 알고리즘입니다. 시작 정점에서 다른 모든 정점까지의 최단 경로를 구할 수 있습니다. 주요 특징은 다음과 같습니다:

• BFS와 비슷하지만, 가중치(거리)를 고려하며 우선순위 큐를 활용합니다.
• 최적화된 시간 복잡도는 우선순위 큐를 활용하여 O((V + E) log V)입니다.
• 목적지를 찾기 위한 알고리즘이 아니라 그래프 전체를 탐색하며 최단 경로를 구합니다.

---

코드 분석

헤더 파일과 기본 구조

#include <iostream>
#include <vector>
#include <queue>
#include <climits> // INT_MAX 정의
using namespace std;

1. #include <iostream>: 표준 입출력 라이브러리입니다.
2. #include <vector>: 동적 배열(벡터)을 사용하기 위해 포함합니다.
3. #include <queue>: 우선순위 큐를 사용하기 위해 포함합니다.
4. #include <climits>: 최댓값 상수를 제공하는 헤더로, 최단 거리 초기값으로 사용합니다(INT_MAX).
5. using namespace std;: 표준 네임스페이스를 사용합니다.

---

그래프 표현 및 생성 함수

그래프 표현

vector<vector<int>> adjacent; // 인접 행렬로 그래프를 표현

• adjacent: 그래프를 표현하는 2차원 벡터입니다.
  • adjacent[i][j]는 정점 i에서 정점 j로의 간선 가중치를 나타냅니다.
  • -1은 간선이 없음을 의미합니다.

그래프 생성

void CreateGraph()
{
    adjacent = vector<vector<int>>(6, vector<int>(6, -1)); // 6x6 크기의 인접 행렬 생성
    adjacent[0][1] = adjacent[1][0] = 15; // 양방향 간선 (0 <-> 1)
    adjacent[0][3] = adjacent[3][0] = 35; // 양방향 간선 (0 <-> 3)
    adjacent[1][2] = adjacent[2][1] = 5;  // 양방향 간선 (1 <-> 2)
    adjacent[1][3] = adjacent[3][1] = 10; // 양방향 간선 (1 <-> 3)
    adjacent[3][4] = adjacent[4][3] = 5;  // 양방향 간선 (3 <-> 4)
    adjacent[5][4] = adjacent[4][5] = 5;  // 양방향 간선 (4 <-> 5)
}

1. adjacent 초기화:
   • vector<vector<int>>(6, vector<int>(6, -1)): 6x6 크기의 2차원 벡터를 생성하고, 모든 값을 -1로 초기화합니다.
   • -1은 간선이 없음을 의미합니다.
2. 간선 설정:
   • 양방향 간선을 나타내기 위해 adjacent[i][j]와 adjacent[j][i]를 동일한 가중치로 설정합니다.
   • 예: adjacent[0][1] = adjacent[1][0] = 15은 정점 0과 1 사이의 간선 가중치가 15임을 나타냅니다.

---

VertexCost 구조체 정의

struct VertexCost
{
    VertexCost(int cost, int vertex) : cost(cost), vertex(vertex) {}
    bool operator>(const VertexCost& other) const
    {
        return cost > other.cost;
    }
    int cost;
    int vertex;
};

1. VertexCost 정의:
   • 특정 정점까지의 비용(cost)과 해당 정점(vertex) 정보를 저장합니다.
2. 비교 연산자 오버로딩:
   • operator>: priority_queue에서 최소 힙을 사용하기 위해 비용이 작은 것을 우선 처리하도록 정의합니다.

---

다익스트라 알고리즘 함수

void Dijkstra(int here)
{
    priority_queue<VertexCost, vector<VertexCost>, greater<VertexCost>> pq;
    vector<int> best(6, INT_MAX); // 각 정점까지의 최단 경로 비용
    vector<int> parent(6, -1);   // 경로 추적을 위한 부모 정점 저장

    pq.push(VertexCost(0, here)); // 시작 정점을 큐에 추가
    best[here] = 0;               // 시작 정점의 비용을 0으로 설정
    parent[here] = here;          // 시작 정점의 부모를 자기 자신으로 설정

1. 자료구조 초기화:
   • 우선순위 큐: 비용이 작은 경로를 우선 탐색합니다.
     • priority_queue<VertexCost, vector<VertexCost>, greater<VertexCost>> pq
     • greater<VertexCost>를 사용하여 최소 힙으로 동작합니다.
   • best 벡터: 각 정점까지의 최단 거리 비용을 저장하며, 초기값은 INT_MAX(무한대)입니다.
   • parent 벡터: 최단 경로를 추적하기 위해 부모 정점을 저장합니다.
2. 시작 정점 초기화:
   • 시작 정점을 큐에 추가하고, 비용을 0으로 설정합니다.

---

메인 루프

    while (!pq.empty())
    {
        VertexCost v = pq.top();
        pq.pop();

        int cost = v.cost;
        here = v.vertex;

        if (best[here] < cost) // 더 짧은 경로가 이미 발견된 경우
        {
            continue;
        }

        cout << "방문: " << here << endl;

1. 우선순위 큐에서 가장 작은 비용의 정점 꺼내기:
   • pq.top(): 큐에서 가장 작은 비용을 가진 정점을 가져옵니다.
   • pq.pop(): 가져온 정점을 큐에서 제거합니다.
2. 이미 더 짧은 경로가 발견된 경우 스킵:
   • if (best[here] < cost): 현재 비용이 최단 비용보다 크다면 스킵합니다.

---

인접 정점 탐색

        for (int there = 0; there < 6; there++)
        {
            if (adjacent[here][there] == -1) // 연결되지 않은 정점 스킵
            {
                continue;
            }

            int nextCost = best[here] + adjacent[here][there];
            if (nextCost >= best[there]) // 더 나쁜 경로는 스킵
            {
                continue;
            }

            best[there] = nextCost;
            parent[there] = here;
            pq.push(VertexCost(nextCost, there));
        }
    }
}

1. 유효한 간선만 탐색:
   • adjacent[here][there] == -1이면 간선이 없으므로 스킵합니다.
2. 비용 갱신 조건:
   • nextCost: 현재 정점까지의 최단 비용 + 현재 정점에서 인접 정점으로의 가중치.
   • nextCost >= best[there]: 이미 더 짧은 경로를 찾았다면 스킵합니다.
3. 최단 비용 갱신:
   • best[there] = nextCost: 더 짧은 경로를 발견했으므로 갱신합니다.
   • parent[there] = here: 현재 정점을 인접 정점의 부모로 설정합니다.
   • 큐에 인접 정점을 추가합니다.

---

메인 함수

int main()
{
    CreateGraph();
    Dijkstra(0); // 정점 0에서 시작
    return 0;
}

1. 그래프 생성:
   • CreateGraph()을 호출하여 그래프를 초기화합니다.
2. 다익스트라 실행:
   • Dijkstra(0)을 호출하여 정점 0에서 시작하는 최단 경로를 찾습니다.

---