다익스트라 알고리즘

그래프 구조: 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 <queue> #include <vector> void dijkstra_optimized(int start) { vector<int> dist(V, INF); priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; dist[start] = 0; pq.push({0, start}); while (!pq.empty()) { int cost = pq.top().first; int here = pq.top().second; pq.pop(); if (dist[here] < cost) continue; for (auto& edge : graph[here]) { int there = edge.first; int nextDist = cost + edge.second; if (nextDist < dist[there]) { dist[there] = nextDist; pq.push({nextDist, there}); } } } }

// 도로망에서 최단 경로 찾기 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 사용 (오버플로우 주의)