LV16 다익스트라 알고리즘 (Dijkstra's Algorithm)

그래프 구조: B (5만원) 50↗ ↘5 A 10 C 20↘ ↗25 D A→C 직접: 999999 (불가능) A→D→B→C: 20 + 10 + 5 = 35만원 ✅ (최적)

#include <iostream> #define NOT 999999 int map[4][4] = { {0, 50, NOT, 20 }, // A에서 각 노드까지 {NOT, 0, 5, NOT}, // B에서 각 노드까지 {NOT, NOT, 0, NOT}, // C에서 각 노드까지 {NOT, 10, 25, 0 } // D에서 각 노드까지 }; int result[4] = {0, 50, NOT, 20}; // 최소비용 테이블 int visited[4] = {1, 0, 0, 0}; // 방문 여부 (A는 시작점이므로 방문됨) // 방문하지 않은 노드 중 최소 비용 노드 찾기 int findMin() { int min = 987654321; int minIndex = -1; for (int i = 0; i < 4; i++) { if (visited[i] == 0 && result[i] < min) { min = result[i]; minIndex = i; } } return minIndex; } void dijkstra() { int minIndex = 0; for (int i = 0; i < 3; i++) // 3번 반복 (시작점 제외한 나머지 노드) { // 1. via가 0인 곳 중에 최소값을 찾기 minIndex = findMin(); // 2. a vs b 해서 a가 더 저렴하면 전광판에 갱신해준다. // a = 경유지까지 가는 비용 + 경유지에서 목적지까지 가는 비용 // b = A에서 목적지까지 가는 비용 for (int j = 0; j < 4; j++) { int a = result[minIndex] + map[minIndex][j]; // 경유 비용 int b = result[j]; // 직행 비용 if (a < b) { result[j] = a; // 더 저렴하면 갱신 } } visited[minIndex] = 1; // 해당 노드를 거쳐서 지나가는 비용과 값을 비교 완료 } // 결과 출력 std::cout << "=== 최단 거리 결과 ===" << std::endl; char nodes[] = {'A', 'B', 'C', 'D'}; for (int i = 0; i < 4; i++) { std::cout << "A → " << nodes[i] << ": " << result[i] << "만원" << std::endl; } } int main() // char main()에서 int main()으로 수정 { dijkstra(); return 0; }

// 방문하지 않은 노드 중 최소 비용 노드 찾기 int findMin() { int min = 987654321; int minIndex = -1; for (int i = 0; i < 4; i++) { if (visited[i] == 0 && result[i] < min) { min = result[i]; minIndex = i; } } return minIndex; }

// 경유지를 통한 비용 vs 직행 비용 비교 int a = result[minIndex] + map[minIndex][j]; // 경유 비용 int b = result[j]; // 현재 최소 비용 if (a < b) { result[j] = a; // 더 저렴하면 갱신 }

#include <iostream> #include <vector> #include <queue> #include <tuple> // 또는 <utility> (std::pair 사용) #define NOT 999999 #define INF 987654321 // 그래프 데이터 (인접 행렬 유지) int map[4][4] = { {0, 50, NOT, 20 }, {NOT, 0, 5, NOT}, {NOT, NOT, 0, NOT}, {NOT, 10, 25, 0 } }; int result[4]; // 최단 거리 테이블 void dijkstra(int start) { // 1. 최단 거리 테이블 초기화 (무한대) for (int i = 0; i < 4; i++) { result[i] = INF; } // 2. 우선순위 큐 선언 (Min-Heap: 비용이 작은 것이 위로) // 자료형: <비용, 정점번호> pair std::priority_queue<std::pair<int, int> , std::vector<std::pair<int, int>> , std::greater<std::pair<int, int>>> pq; // 3. 시작 노드 초기화 result[start] = 0; pq.push({ 0, start }); // {비용, 노드} while (!pq.empty()) { // 비용이 가장 적은 노드 꺼내기 int currentCost = pq.top().first; int currentNode = pq.top().second; pq.pop(); // 현재 꺼낸 비용이 이미 기록된 최소 비용보다 크다면 스킵 (이미 처리된 경로) if (currentCost > result[currentNode]) continue; // 인접 노드 확인 (인접 행렬이므로 0~3 반복) for (int nextNode = 0; nextNode < 4; nextNode++) { // 연결되어 있지 않거나 자기 자신인 경우 패스 if (map[currentNode][nextNode] == NOT || map[currentNode][nextNode] == 0) continue; int nextCost = currentCost + map[currentNode][nextNode]; // 더 적은 비용으로 갈 수 있다면 갱신 후 큐에 삽입 if (nextCost < result[nextNode]) { result[nextNode] = nextCost; pq.push({ nextCost, nextNode }); } } } // 결과 출력 std::cout << "=== 최단 거리 결과 ===" << std::endl; char nodes[] = { 'A', 'B', 'C', 'D' }; for (int i = 0; i < 4; i++) { // 경로가 없는 경우 처리 if (result[i] == INF) std::cout << nodes[start] << " -> " << nodes[i] << ": 갈 수 없음" << std::endl; else std::cout << nodes[start] << " -> " << nodes[i] << ": " << result[i] << "만원" << std::endl; } } int main() { dijkstra(0); // 0번 노드(A)에서 시작 return 0; }

// 도로망에서 최단 경로 찾기 struct Road { int to; int distance; int time; }; void findShortestRoute(int start, int destination) { // 다익스트라로 최단 경로 계산 }

// 패킷이 가장 빠른 경로로 전송되도록 void findOptimalRoute(int source, int target) { // 지연시간을 가중치로 하여 최적 경로 계산 }

// 캐릭터가 장애물을 피해 목적지까지 void findPath(Point start, Point goal) { // 맵을 그래프로 변환하여 최단 경로 계산 }

다익스트라는 음수 가중치를 처리할 수 없습니다. 음수 가중치가 있다면 벨만-포드 알고리즘 사용!

// 인접 행렬 vs 인접 리스트 int matrix[V][V]; // 메모리: O(V²), 밀집 그래프에 적합 vector<vector<pair<int,int>>> adj; // 메모리: O(V+E), 희소 그래프에 적합

#define INF 987654321 // 충분히 큰 값으로 설정 // 또는 #define INF INT_MAX 사용 (오버플로우 주의)