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

 

그래프 알고리즘 중 하나이다. 가중치가 있는 그래프에서 특정 노드로부터 최단 거리(Shortest Path)를 찾는데 사용된다.

그래프의 시작 노드에서 다른 모든 노드까지의 최단 거리를 계산한다.
가중치가 있는 비음수 그래프에 적용 가능하다.

시간 복잡도

우선순위 큐를 사용하면 O((V + E)logV)

여기서 V는 정점 수, E는 간선 수이다.

• 입력
  그래프 G = (V, E): V는 정점 집합, E는 간선 집합
  시작 노드 S
• 출력
  시작 노드 S에서 다른 모든 노드까지의 최단 거리

1. 시작 노드의 최단 거리를 0으로 설정하고, 다른 모든 노드의 거리는 ∞로 초기화한다.
2. 방문하지 않은 노드 중 최단 거리가 가장 작은 노드를 선택한다.
3. 선택된 노드의 인접 노드를 확인하여 현재 경로를 통해 인접 노드로 가는 비용이 더 적으면 갱신한다.
4. 모든 노드를 방문할 때까지 반복한다.

import java.util.*;

public 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 Integer.compare(this.weight, other.weight);
        }
    }

    public static void dijkstra(int[][] graph, int source) {
        int n = graph.length; // 정점 개수
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];

        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(source, 0));

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

            if (visited[u]) continue;
            visited[u] = true;

            for (int v = 0; v < n; v++) {
                if (graph[u][v] != 0 && !visited[v]) { // 간선이 존재하고 방문하지 않은 노드
                    int newDist = dist[u] + graph[u][v];
                    if (newDist < dist[v]) {
                        dist[v] = newDist;
                        pq.add(new Node(v, newDist));
                    }
                }
            }
        }

        System.out.println("최단 거리:");
        for (int i = 0; i < n; i++) {
            System.out.println("노드 " + source + " → 노드 " + i + ": " + dist[i]);
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 4, 0, 0, 0, 0, 0, 8, 0},
            {4, 0, 8, 0, 0, 0, 0, 11, 0},
            {0, 8, 0, 7, 0, 4, 0, 0, 2},
            {0, 0, 7, 0, 9, 14, 0, 0, 0},
            {0, 0, 0, 9, 0, 10, 0, 0, 0},
            {0, 0, 4, 14, 10, 0, 2, 0, 0},
            {0, 0, 0, 0, 0, 2, 0, 1, 6},
            {8, 11, 0, 0, 0, 0, 1, 0, 7},
            {0, 0, 2, 0, 0, 0, 6, 7, 0}
        };
        dijkstra(graph, 0); // 시작 노드 0
    }
}

int[][] graph = {  
        {0, 4, 0, 0, 0, 0, 0, 8, 0},  
        {4, 0, 8, 0, 0, 0, 0, 11, 0},  
        {0, 8, 0, 7, 0, 4, 0, 0, 2},  
        {0, 0, 7, 0, 9, 14, 0, 0, 0},  
        {0, 0, 0, 9, 0, 10, 0, 0, 0},  
        {0, 0, 4, 14, 10, 0, 2, 0, 0},  
        {0, 0, 0, 0, 0, 2, 0, 1, 6},  
        {8, 11, 0, 0, 0, 0, 1, 0, 7},  
        {0, 0, 2, 0, 0, 0, 6, 7, 0}  
};

위 2차원 배열 graph는 그래프(네트워크)를 인접 행렬(Adjacency Matrix)로 표현한 것이다. 이를 통해 그래프의 노드(정점)와 엣지(간선)을 나타낼 수 있다.
9개의 노드와 가중치가 있는 간선으로 구성되어 있고, 시작 노드는 0이다.

그래프 해석

1. 행(Row): 그래프의 시작 정점
2. 열(Column): 그래프의 도착 정점
3. 배열의 값: 시작 정점과 도착 정점 사이의 간선 가중치
4. 예시
5. graph[0][1] = 4

• 노드 0과 노드 1 사이에 가중치 4인 간선이 있음

2. graph[3][4] = 9

• 노드 3과 노드 4 사이에 가중치 9인 간선이 있음

3. graph[2][3] = 7

• 노드 2와 노드 3 사이에 가중치 7인 간선이 있음

4. graph[5][6] = 2

• 노드 5와 노드 6 사이에 가중치 2인 간선이 있음

정점 간 연결이 없으면 0으로 표시한다. graph[0][0], graph[1][1], graph[2][2] 등은 자기 자신과의 관계에선 연결이 없기에 모두 0이다.

• 결과
  노드 0에서 각 노드까지의 최단 거리가 출력된다.

Node 클래스

우선순위 큐(Priority Queue)에서 정렬 기준을 제공하기 위해 정의된 클래스이다.

필드

• int vertex: 노드의 번호를 나타낸다.
• int weight: 출발 노드로부터 해당 노드까지의 거리(가중치)를 나타낸다.

compareTo 메서드

노드를 정렬할 때 weight를 기준으로 비교하여 우선순위 큐에서 최단 거리 노드가 먼저 나오게 설정한다.

다익스트라 알고리즘은 입력으로 가중치 그래프와 시작 노드를 받아 최단 거리를 계산한다.

compareTo는 객체 간 정렬 순서를 정의하기 위해 사용하는 메서드이다. 이 메서드는 Comparable 인터페이스를 구현하여 객체를 자연 정렬(Natural Ordering) 기준으로 정렬할 때 사용된다.

Comparable 인터페이스는 다음과 같이 정의되어 있다.

public interface Comparable<T> {
    public int compareTo(T o);
}

• 매개변수 o: 비교할 대상 객체
• 반환값
  • < 0: 현재 객체가 비교 대상 객체보다 작음
  • 0: 현재 객체가 비교 대상 객체와 같음
  • > 0: 현재 객체가 비교 대상 객체보다 큼
• 오름차순 정렬

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

• 내림차순 정렬

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

• String 클래스

@Override
public int compareTo(String anotherString) {
    return this.compareTo(anotherString); // 사전순 비교
}

1. 입력 그래프

• graph는 인접 행렬 형태로 주어진다.
• graph[i][j]는 정점 i와 정점 j 사이 간선의 가중치를 나타낸다.
• 값이 0이면 두 정점 사이에 간선이 없는 것을 의미한다.

2. 배열 초기화

int[] dist = new int[n];
boolean[] visited = new boolean[n];

Arrays.fill(dist, Integer.MAX_VALUE); // 초기 거리 무한대로 설정
dist[source] = 0; // 시작 정점의 거리는 0

 

dist: 시작 노드에서 각 노드까지의 최단 거리를 저장
visited: 각 노드의 방문 여부를 기록

 

3. 우선순위 큐 초기화

PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(source, 0));

• 시작 노드를 우선순위 큐에 추가한다.
• 우선순위 큐는 가장 짧은 거리(최소 가중치)를 가진 노드를 먼저 처리한다.

4. 알고리즘 반복

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

    if(visited[u]) continue;
    visited[u] = true;
}

• 우선순위 큐에서 현재 거리 기준으로 가장 가까운 노드를 가져온다.
• 이미 방문한 노드는 건너뛴다.

5) 인접 노드 업데이트

for(int v = 0; v < n; v++){
    if(graph[u][v] != 0 && !visited[v]){ // 간선이 존재하고 방문하지 않은 노드
        int newDist = dist[u] + graph[u][v];
        if(newDist < dist[v]){
            dist[v] = newDist; // 거리 갱신
            pq.add(new Node(v, newDist)); // 갱신된 거리로 우선순위 큐에 추가
        }
    }
}

• 현재 노드 u의 모든 인접 노드 v 확인
  1. graph[u][v] != 0: u와 v가 연결돼 있는지 확인
  2. !visited[v]: v가 아직 방문되지 않았는지 확인
  3. 최단 거리 계산
     • newDist = dist[u] + graph[u][v]로 새 경로의 거리를 계산
  4. 갱신 조건
     • newDist < dist[v]일 때 v로의 최단 거리를 갱신
  5. 갱신된 노드를 우선순위 큐에 추가

6) 결과 출력

System.out.println("최단 거리:");
for (int i = 0; i < n; i++) {
    System.out.println("노드: " + source + " -> 노드 " + i + ": " + dist[i]);
}

• 시작 노드에서 모든 노드까지의 최단 거리를 출력
• 알고리즘 응용 사례
  지도 네비게이션: 도시 간 최단 경로 계산
  네트워크 라우팅: 패킷 전송시 최단 경로 찾기
  자율주행: 로봇의 최적 이동 경로 계산