[java] 다익스트라 알고리즘

04 Dec 2023

java

다익스트라 알고리즘은 그래프에서 한 정점에서 모든 다른 정점까지의 최단 경로를 구하는 알고리즘입니다. 이 알고리즘은 음수 가중치를 포함한 그래프에서는 동작하지 않습니다.

알고리즘 동작 원리

시작 정점을 선택하고 시작 정점으로부터의 거리 배열을 초기화합니다. 시작 정점의 거리는 0으로 설정하고, 나머지 정점들의 거리는 무한대로 초기화합니다.
아직 방문하지 않은 정점 중에서 거리가 가장 짧은 정점을 선택합니다.
선택한 정점과 연결된 정점들의 거리를 갱신합니다. 기존의 거리보다 작은 값으로 갱신되는 경우, 해당 정점의 거리를 업데이트합니다.
모든 정점을 방문할 때까지 2, 3번 과정을 반복합니다.

자바로 구현한 다익스트라 알고리즘 예제

아래는 자바로 다익스트라 알고리즘을 구현한 예제입니다. 해당 예제는 인접 행렬을 통해 그래프를 표현하고, 시작 정점으로부터의 최단 거리 배열을 반환합니다.

public class Dijkstra {
    private static final int INF = Integer.MAX_VALUE;

    public int[] dijkstra(int[][] graph, int start) {
        int vertices = graph.length;
        int[] distances = new int[vertices];
        boolean[] visited = new boolean[vertices];

        Arrays.fill(distances, INF);
        distances[start] = 0;

        for (int i = 0; i < vertices - 1; i++) {
            int minDistance = INF;
            int minVertex = -1;

            for (int j = 0; j < vertices; j++) {
                if (!visited[j] && distances[j] < minDistance) {
                    minDistance = distances[j];
                    minVertex = j;
                }
            }

            visited[minVertex] = true;

            for (int j = 0; j < vertices; j++) {
                if (!visited[j] && graph[minVertex][j] != 0) {
                    distances[j] = Math.min(distances[j], distances[minVertex] + graph[minVertex][j]);
                }
            }
        }

        return distances;
    }
}

사용 예제

위에서 구현한 다익스트라 알고리즘을 사용해보겠습니다. 다음은 그래프를 생성하고 알고리즘을 실행하여 시작 정점으로부터의 최단 거리를 출력하는 예제입니다.

public class Main {
    public static void main(String[] args) {
        int[][] graph = {
            {0, 2, 5, 0, 0, 0 },
            {2, 0, 3, 1, 0, 0 },
            {5, 3, 0, 3, 1, 5 },
            {0, 1, 3, 0, 2, 0 },
            {0, 0, 1, 2, 0, 0 },
            {0, 0, 5, 0, 0, 0 }
        };

        Dijkstra dijkstra = new Dijkstra();
        int start = 0;

        int[] distances = dijkstra.dijkstra(graph, start);

        System.out.println("Starting from vertex " + start);
        for (int i = 0; i < distances.length; i++) {
            System.out.println("Shortest distance to vertex " + i + " : " + distances[i]);
        }
    }
}

위 예제의 출력 결과는 다음과 같습니다.

Starting from vertex 0
Shortest distance to vertex 0 : 0
Shortest distance to vertex 1 : 2
Shortest distance to vertex 2 : 5
Shortest distance to vertex 3 : 3
Shortest distance to vertex 4 : 4
Shortest distance to vertex 5 : 10

이처럼 다익스트라 알고리즘은 시작 정점으로부터 다른 모든 정점까지의 최단 거리를 계산하는 간단하면서도 유용한 알고리즘입니다.

알고리즘 동작 원리

자바로 구현한 다익스트라 알고리즘 예제

사용 예제

참고 자료