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

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

다익스트라 알고리즘은 가중치가 있는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 그리디(greedy) 방식을 기반으로 하며, 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger W. Dijkstra)에 의해 제안되었습니다.

---

다익스트라 알고리즘의 특징

1. 가중치가 음수가 아닌 그래프에만 적용 가능:
   • 가중치가 음수인 경우, 이 알고리즘은 최적의 결과를 보장할 수 없습니다.
2. 단일 시작점에서 다른 모든 정점까지의 최단 경로를 계산:
   • 한 정점에서 다른 모든 정점까지의 최단 경로를 계산.
   • 시작 정점에서 특정 정점까지의 최단 경로를 계산할 수 있습니다.
3. 시간 복잡도:
   • 시간 복잡도: O((V+E)logV) (우선순위 큐 사용 시).

---

작동 원리

1. 입력:
   • 그래프 G=(V,E), 시작 정점 S.
   • V: 정점의 집합.
   • E: 간선의 집합.
   • 각 간선은 (u,v,w)로 표시되며, u와 v는 정점, w는 가중치입니다.
2. 초기화:
   • dist[]: 시작 정점에서 각 정점까지의 최단 거리를 저장하는 배열.
     • dist[S]=0, 시작 정점에서 자신까지의 거리는 0.
     • 나머지 정점의 거리 dist[]는 ∞\infty∞(무한대)로 초기화.
   • visited[]: 방문 여부를 표시하는 배열. 모든 정점은 초기값으로 미방문 상태.
3. 최단 거리 갱신:
   • 시작 정점에서 출발하여 인접한 정점들의 거리를 갱신합니다.
   • 아직 방문하지 않은 정점 중에서 현재까지의 최단 거리 값이 가장 작은 정점을 선택합니다.
   • 선택한 정점의 인접한 정점들에 대해 새로운 경로의 거리가 기존 거리보다 짧으면 갱신합니다.
4. 반복:
   • 모든 정점이 방문되거나, 더 이상 갱신할 거리가 없을 때까지 반복합니다.
5. 출력:
   • dist[] 배열을 출력하여 시작 정점에서 각 정점까지의 최단 거리를 확인합니다.

 

---

---

import java.util.*;

class Dijkstra {
    static class Node implements Comparable<Node> {
        int vertex, weight;

        Node(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node other) {
            return this.weight - other.weight; // 가중치 기준 오름차순
        }
    }

    public static int[] dijkstra(int n, int[][] edges, int start) {
        // 그래프를 인접 리스트로 표현
        List<List<Node>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(new Node(edge[1], edge[2]));
        }

        // 거리 배열 초기화
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        // 우선순위 큐 (최소 힙)
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));

        // 방문 여부 체크
        boolean[] visited = new boolean[n];

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int u = current.vertex;

            if (visited[u]) continue; // 이미 방문한 정점이면 건너뜀
            visited[u] = true;

            // 인접 정점 거리 갱신
            for (Node neighbor : graph.get(u)) {
                int v = neighbor.vertex;
                int weight = neighbor.weight;

                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.offer(new Node(v, dist[v]));
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {
            {0, 1, 2}, {0, 2, 4}, {1, 2, 1},
            {1, 3, 7}, {2, 4, 3}, {3, 4, 1}
        };
        int start = 0;

        int[] distances = dijkstra(n, edges, start);
        System.out.println("최단 거리: " + Arrays.toString(distances));
    }
}

 

장점

1. 빠른 성능:
   • 우선순위 큐를 사용하여 효율적으로 최단 거리를 계산합니다.
2. 직관적인 구현:
   • 단일 시작점 문제를 해결하는 데 적합하며, 구현이 비교적 간단합니다.

단점

1. 음수 가중치 처리 불가:
   • 음수 가중치가 포함된 그래프에서는 사용 불가능합니다.
2. 단일 시작점:
   • 여러 시작점에서 최단 경로를 계산하려면 반복 실행해야 합니다.

---

적용 사례

• 네트워크 라우팅: 최단 경로를 기반으로 데이터 패킷 전송.
• 지도 서비스: 두 지점 간 최단 경로 계산(GPS, 내비게이션).
• 물류 및 공급망: 최소 비용 경로 탐색.

다익스트라 알고리즘은 효율적이고 널리 사용되는 알고리즘으로, 가중치가 음수가 없는 환경에서 강력한 성능을 발휘합니다. 😊