다익스트라 (Dijkstra)

1. 개요

• 다익스트라 알고리즘은 가중치가 있는 그래프에서 두 노드 간의 최단 경로를 찾기 위한 알고리즘이다.
• 주로 네트워크 라우팅 프로토콜이나 GPS 장치에서 경로를 계획하는 데 사용됩니다.
• 이 알고리즘은 그래프의 한 정점에서 다른 모든 정점까지의 최단 거리를 계산한다.

2. 특징

• 가중치 포함: 모든 간선은 양의 가중치를 가진다. 음수 가중치가 있는 경우, 알고리즘이 올바르게 작동하지 않는다.
• 그리디 알고리즘: 다익스트라 알고리즘은 현재 상태에서 최적의 해를 선택하는 그리디(Greedy) 방법론을 사용한다.
• 시간 복잡도: 우선순위 큐(Priority Queue)를 사용할 경우 O((V+E)logV)이다. (V는 정점의 수, E는 간선의 수)

3. 코드

import java.util.Arrays;
import java.util.PriorityQueue;

class Edge implements Comparable<Edge> {
    int node;
    int cost;

    Edge(int node, int cost) {
        this.node = node;
        this.cost = cost;
    }

    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.cost, other.cost);
    }
}

public class DijkstraAlgorithm {

    public static int[] dijkstra(int[][] graph, int start) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        int[] distances = new int[graph.length];
        boolean[] visited = new boolean[graph.length];

        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[start] = 0;
        pq.add(new Edge(start, 0));

        while (!pq.isEmpty()) {
            Edge current = pq.poll();

            if (visited[current.node]) continue;
            visited[current.node] = true;

            for (int i = 0; i < graph[current.node].length; i++) {
                if (graph[current.node][i] != 0 && !visited[i]) {
                    int newDist = distances[current.node] + graph[current.node][i];
                    if (newDist < distances[i]) {
                        distances[i] = newDist;
                        pq.add(new Edge(i, newDist));
                    }
                }
            }
        }

        return distances;
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 2, 0, 6, 0},
            {2, 0, 3, 8, 5},
            {0, 3, 0, 0, 7},
            {6, 8, 0, 0, 9},
            {0, 5, 7, 9, 0},
        };

        int[] distances = dijkstra(graph, 0);
        System.out.println("최단 거리 배열: " + Arrays.toString(distances));
    }
}