Algorithm

[Algorithm] 그래프 최단 경로 알고리즘 - 다익스트라(Dijkstra)

Rubi ❤️ 2025. 5. 22. 20:53
728x90
반응형

 

✅ 핵심 개념 정리

항목 내용
알고리즘 이름 다익스트라 (Dijkstra)
목적 단일 출발점에서 다른 모든 정점까지의 최단 거리 계산
조건 간선의 가중치는 0 이상 (음수 X)
시간복잡도 O((V + E) log V) (우선순위 큐 사용 시)
사용 구조 Greedy (탐욕법) + Priority Queue (최소힙)

 

❗️다익스트라(Dijkstra) 알고리즘은 그래프에서 하나의 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘
가중치가 음수가 아닌 그래프에서만 동작

💡 동작 원리

문제 상황 예시:

지도 위에 여러 도시가 있고, 도시 간 거리(비용)가 주어진다.
당신은 출발 도시에서 다른 도시로 최단 거리로 가고 싶다.

✅ 다익스트라 알고리즘 절차 (요약)

  1. 거리 배열 초기화
    • 출발점: 0
    • 나머지: INF (도달 불가로 초기화)
  2. 우선순위 큐(PQ)에 시작 노드를 삽입
    • PQ는 (거리, 정점) 쌍을 저장
    • 항상 가장 가까운 정점부터 처리
  3. 큐에서 정점 꺼내기 + 인접 노드 확인
    • 인접 노드를 통해 더 짧은 경로가 있으면 갱신하고 큐에 추가
  4. 모든 정점이 큐에서 한 번씩 처리될 때까지 반복

🔄 예시 그래프

정점: 1, 2, 3, 4  
간선:  
1 —(2)—> 2  
1 —(5)—> 3  
2 —(1)—> 3  
3 —(3)—> 4

시작점 = 1

정점 최단거리(초기)
1 0
2 ∞
3 ∞
4 ∞
  • 1번에서 2번 → 2
  • 1번에서 3번 → 5
  • 2번에서 3번 → 2 + 1 = 3 → 더 짧음 → 갱신
  • 3번에서 4번 → 3 + 3 = 6

최종 거리 배열: [0, 2, 3, 6]

✅ 의사코드 (Pseudo Code)

function dijkstra(start):
    dist[] = INF
    dist[start] = 0
    pq = priority_queue({0, start}) // 거리 기준 최소 힙

    while pq is not empty:
        (cur_dist, u) = pq.pop()
        if dist[u] < cur_dist:
            continue // 이미 더 짧게 방문됨

        for each neighbor v of u:
            if dist[v] > dist[u] + weight(u, v):
                dist[v] = dist[u] + weight(u, v)
                pq.push({dist[v], v})

✅ 다익스트라의 핵심 포인트

요소 설명
우선순위 큐 사용 이유 항상 가장 가까운 노드부터 처리하기 위함
거리 배열 필요 이유 최단 거리 기록 및 갱신 확인
visited 배열 불필요 우선순위 큐에서 "이미 최단거리로 방문"했는지 비교로 대체

⚠️ 주의: 다익스트라가 실패하는 경우

  • 음수 가중치가 있는 경우: 최단 경로가 나중에 더 짧아지는 상황이 발생할 수 있어 정확하지 않음
  • 음수 간선이 있으면 → 벨만포드(Bellman-Ford) 또는 플로이드-워셜(Floyd-Warshall) 사용

✅ 시각적 직관 (간단 요약)

  1. 초기화: 모든 노드는 무한대 거리, 시작 노드는 0
  2. 가까운 노드부터 뻗어나감 (BFS처럼)
  3. 더 짧은 경로가 발견되면 갱신
  4. 우선순위 큐는 가장 짧은 거리 기준으로 다음 노드 선택

✅ 예시 C++ 구현 코드

vector<int> dijkstra(int start) {
    vector<int> dist(n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;

    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [curDist, u] = pq.top(); pq.pop();
        if (dist[u] < curDist) continue;

        for (auto [v, weight] : graph[u]) {
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}

🚀 정리

개념 설명
그래프 조건 가중치 ≥ 0, 연결 그래프
알고리즘 유형 그리디 (Greedy) + 최소 힙 (Priority Queue)
시간복잡도 O((V + E) log V) (heap 사용 시)
데이터 구조 거리 배열, 우선순위 큐, 인접 리스트
주의사항 음수 간선 X

 

728x90
반응형