다익스트라 알고리즘

📌 다익스트라 알고리즘이란?

Dijkstra Algorithm은 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다.
BFS와 매우 유사한 흐름을 따르지만, 간선에 가중치가 있는 그래프에서만 사용되며, 가장 적은 비용(=거리)을 고려한다는 점에서 다릅니다.

---

📐 코드 전체 구조 이해

struct Vertex {};
vector<Vertex> vertices;
vector<vector<int>> adjacent; // 인접 행렬

• Vertex: 정점 정보를 담을 구조체 (현재는 사용 안함)
• adjacent: 정점 간 간선 비용을 저장하는 2차원 배열

---

🧱 그래프 생성 함수

void CreateGraph()
{
    vertices.resize(6);
    adjacent = vector<vector<int>>(6, vector<int>(6, -1));

    adjacent[0][1] = 15;
    adjacent[0][3] = 35;
    adjacent[1][0] = 15;
    adjacent[1][2] = 5;
    adjacent[1][3] = 10;
    adjacent[3][4] = 5;
    adjacent[5][4] = 5;
}

• adjacent[i][j]: i에서 j로 가는 간선의 가중치
• -1: 두 정점이 연결되어 있지 않음을 의미
• 무방향 가중치 그래프를 만들고 있음

---

🧠 다익스트라 알고리즘 핵심 함수

📦 구조체 정의

struct VertexCost {
    int vertex;
    int cost;
};

• 정점 번호 + 현재까지 누적 비용을 함께 저장

---

🔧 변수 초기화

list<VertexCost> discovered;
vector<int> best(6, INT32_MAX);
vector<int> parent(6, -1);

discovered.push_back({ here, 0 });
best[here] = 0;
parent[here] = here;

• discovered: 아직 방문하지 않은 정점들 (큐 아님)
• best: 각 정점까지의 최소 비용
• parent: 경로 추적을 위한 부모 정보
• INT32_MAX: 초기값으로 사용 (거의 무한대처럼 사용)

---

🔁 메인 루프 - 최단 경로 탐색

while (!discovered.empty())
{
    // 가장 비용이 적은 정점 선택
    list<VertexCost>::iterator bestIt;
    int bestCost = INT32_MAX;

    for (auto it = discovered.begin(); it != discovered.end(); it++)
    {
        if (it->cost < bestCost)
        {
            bestCost = it->cost;
            bestIt = it;
        }
    }

    int cost = bestIt->cost;
    here = bestIt->vertex;
    discovered.erase(bestIt);

    if (best[here] < cost) continue;

• 발견 목록에서 가장 비용이 적은 정점을 선택
• 이미 더 좋은 경로로 방문된 경우는 continue 처리

---

🧭 인접 정점 탐색 & 비용 갱신

    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;

        discovered.push_back({ there, nextCost });
        best[there] = nextCost;
        parent[there] = here;
    }
}

• 현재 정점과 연결된 모든 정점을 확인
• 더 낮은 비용으로 도달 가능할 때만 갱신
• discovered에 새롭게 등록하고 비용/부모 정보 업데이트

---

📊 결과 출력

for (int i = 0; i < 6; i++)
    cout << i << " 까지의 거리 : " << best[i] << endl;

for (int i = 0; i < 6; i++)
    cout << i << " 의 부모 번호 : " << parent[i] << endl;

• best[i]: 시작점 → i까지의 최단 거리
• parent[i]: 경로 추적 시 i 정점의 직전 정점

---

🔍 왜 Queue 대신 List?

BFS에서는 먼저 발견한 노드가 먼저 방문된다는 보장이 있어 queue 사용이 적절합니다.
하지만 다익스트라에선 발견된 순서가 아닌 비용이 가장 낮은 정점을 우선 방문해야 하므로 list를 쓰고, 직접 최솟값을 찾습니다.

---

📉 단점 & 최적화 방향

❌ 단점

• 매 루프마다 list를 순회하여 최솟값 탐색 → O(V²)의 시간 복잡도

✅ 개선

• 우선순위 큐 (priority_queue) 사용
  • O(log N) 시간에 가장 비용이 낮은 정점 선택 가능
  • 전체 시간 복잡도: O(E + V log V)

---

🧭 BFS vs Dijkstra vs A*

알고리즘	특징	목적지 정보 사용	가중치 고려
BFS	무가중치 최단 경로	❌	❌
Dijkstra	가중치 기반 최단 경로	❌	✅
A*	목적지까지 효율적으로 탐색	✅	✅ + 휴리스틱

---

📌 핵심 흐름

1. CreateGraph()로 가중치 그래프 구성
2. Dijkstra(start) 호출
3. 발견 목록 discovered에 시작점 등록
4. while 루프로 최솟값 정점 탐색 → 방문
5. 연결된 정점들을 확인하고 비용 갱신
6. best[], parent[] 갱신
7. 모든 정점 처리 후 결과 출력

---

📌 전체 코드

void Dijkstra(int here)
{
    struct VertexCost { int vertex, cost; };

    list<VertexCost> discovered;
    vector<int> best(6, INT32_MAX);
    vector<int> parent(6, -1);

    discovered.push_back({ here, 0 });
    best[here] = 0;
    parent[here] = here;

    while (!discovered.empty())
    {
        auto bestIt = discovered.begin();
        int bestCost = INT32_MAX;
        for (auto it = discovered.begin(); it != discovered.end(); ++it)
            if (it->cost < bestCost) { bestCost = it->cost; bestIt = it; }

        int cost = bestIt->cost;
        here = bestIt->vertex;
        discovered.erase(bestIt);
        if (best[here] < cost) continue;

        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;

            discovered.push_back({ there, nextCost });
            best[there] = nextCost;
            parent[there] = here;
        }
    }

    for (int i = 0; i < 6; i++)
        cout << i << "까지의 거리 : " << best[i] << endl;
}

---