[C++ - TIL] 다익스트라 최단 경로 알고리즘의 핵심 로직과 거리 갱신 원리

🎮 주제 : 다익스트라 최단 경로 알고리즘의 핵심 로직과 거리 갱신 원리

태그 : #C++ #알고리즘 #다익스트라 #최단경로 #그래프 #동적할당

---

📌 학습 요약

• 다익스트라 알고리즘의 본질 : 시작점으로부터 다른 모든 노드까지의 최단 거리를 구하기 위해, 매 단계에서 **"가장 가까운 노드"**를 선택하고 그 노드를 거쳐가는 경로가 더 짧은지 검사하는 그리디(Greedy) 기반 탐색 기범 습득
• 최소값 찾기(find)의 정교화 : 방문하지 않은 노드 중 최소 거리를 선택할 때, 인덱스 초기값을 1로 설정하여 유효한 경로가 없을 경우를 대비하는 예외 처리 로직 강화
• 조건부 거리 갱신(Relaxation) : 현재 노드까지의 거리와 다음 노드로 가는 가중치의 합이 기존에 알고 있던 거리보다 작을 때만 업데이트하는 최적화 조건 정립
• 동적 리사이징(Resize) : 노드 번호가 증가함에 따라 인접 행렬과 상태 배열(visited, distance)을 유연하게 확장하여 다양한 크기의 그래프에 대응

---

🛠 주요 코드 및 구현 상세

1. 방문하지 않은 노드 중 최소 거리 찾기

int find() {
    int index = -1;
    int min = INFINITY;

    for (int i = 0; i < distance.size(); i++) {
        // 아직 방문하지 않았고, 현재 찾은 최소값보다 더 짧은 거리가 있다면 갱신
        if (!visited[i] && distance[i] < min) {
            min = distance[i];
            index = i;
        }
    }
    return index; // 최단 거리 노드의 인덱스 반환 (없으면 -1)
}

2. 다익스트라 핵심 루프와 거리 갱신

void dijkstra(int minIndex) {
    int size = distance.size();

    for (int count = 0; count < size - 1; ++count) {
        visited[minIndex] = true; // 현재 가장 가까운 노드 방문 확정

        for (int i = 0; i < size; ++i) {
            // [갱신 조건]
            // 1. 방문하지 않은 노드여야 함
            // 2. 현재 노드와 연결되어 있어야 함(INFINITY가 아님)
            // 3. 현재를 거쳐가는 것이 기존 경로보다 짧아야 함
            if (!visited[i] &&
                graph[minIndex][i] != INFINITY &&
                distance[minIndex] + graph[minIndex][i] < distance[i]) {
                distance[i] = distance[minIndex] + graph[minIndex][i];
            }
        }

        // 다음 단계에서 방문할 가장 가까운 노드 탐색
        minIndex = find();
        if (minIndex == -1) break; // 더 이상 방문할 수 있는 노드가 없으면 종료
    }
}

---

✅ 주요 문법 및 개념 정리

구문 / 개념 특징 주의 사항

Relaxation (완화)	dist[u] + w < dist[v] 검사	거리 갱신 시 반드시 오버플로우를 고려한 큰 값(INFINITY) 설정 필요
Greedy Choice	매번 find()로 최선의 노드 선택	가중치가 음수인 간선이 있는 경우 다익스트라는 사용 불가
vector.resize()	런타임에 배열 크기 조정	기존 데이터를 유지하면서 확장하는 로직 확인 필요
graph[i][i] = 0	자기 자신으로의 거리 초기화	다익스트라 시작 전 대각 행렬 원소를 0으로 세팅

💡 알고리즘 인사이트 : 왜 size - 1번 반복하는가?

• 정점이 V개일 때, 시작점을 제외한 나머지 V-1개의 정점들에 대해 최단 거리를 확정하면 모든 노드에 대한 탐색이 완료되기 때문

---

✨ 느낀 점

• 단순해 보이는 거리 비교 로직(distance[minIndex] + weight < distance[i])이 수만 개의 경로 중 최적을 찾아내는 핵심 열쇠라는 점이 인상적이었음
• find() 함수에서 인덱스가 1인 경우를 체크하지 않으면 프로그램이 중단될 수 있다는 실습을 통해 방어적 프로그래밍의 중요성을 느낌
• 역할에 따라 find(), update(), dijkstra()로 함수를 분리하니 코드의 가독성이 좋아지고 로직의 흐름을 추적하기 훨씬 수월해짐
• 무한대(INFINITY)를 설정할 때 실제 데이터의 최대 합보다 충분히 큰 값을 사용해야 오류가 없음을 체감함