[java] 자바를 이용한 다익스트라 알고리즘

15 Dec 2023

java

다익스트라 알고리즘은 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘입니다. 이번에는 자바를 이용하여 그래프에서 다익스트라 알고리즘을 구현해보겠습니다.

그래프 표현

먼저, 그래프를 표현하는 방법에 대해 이야기해보겠습니다. 그래프를 표현하는 가장 일반적인 방법은 인접 리스트 또는 인접 행렬을 사용하는 것입니다. 이 예제에서는 간단히 인접 리스트를 사용하도록 하겠습니다.

import java.util.*;

class Graph {
    private int V;
    private List<List<Node>> adj;

    public Graph(int V) {
        this.V = V;
        adj = new ArrayList<>(V);
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
    }

    public void addEdge(int source, int destination, int weight) {
        adj.get(source).add(new Node(destination, weight));
    }

    // ... 다익스트라 알고리즘을 위한 추가 메서드들
}

위의 코드에서 Node 클래스는 정점과 해당 정점까지의 가중치를 표현합니다.

다익스트라 알고리즘

이제 다익스트라 알고리즘을 구현해보겠습니다. 먼저, Graph 클래스에 다익스트라 알고리즘을 수행하는 메서드를 추가할 수 있습니다.

class Graph {
    // ... 그래프 표현 관련 코드

    public int[] dijkstra(int source) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>(V, Comparator.comparingInt(a -> a.weight));
        pq.add(new Node(source, 0));

        while (!pq.isEmpty()) {
            int u = pq.poll().vertex;
            for (Node neighbor : adj.get(u)) {
                int v = neighbor.vertex;
                int weight = neighbor.weight;

                // 최단 경로 업데이트
                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.add(new Node(v, dist[v]));
                }
            }
        }

        return dist;
    }

    // ... 추가적인 메서드들
}

위의 코드에서 dijkstra 메서드는 주어진 출발 정점으로부터의 최단 거리를 포함한 배열을 반환합니다.

이제 해당 Graph 클래스를 사용하여 다익스트라 알고리즘을 실행할 수 있습니다.

public class Main {
    public static void main(String[] args) {
        int V = 5;
        Graph graph = new Graph(V);

        graph.addEdge(0, 1, 9);
        graph.addEdge(0, 2, 6);
        graph.addEdge(0, 3, 5);
        graph.addEdge(0, 4, 3);
        graph.addEdge(2, 1, 2);
        graph.addEdge(2, 3, 4);

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

위의 코드는 그래프를 생성하고 다익스트라 알고리즘을 사용하여 시작 정점으로부터의 최단 거리를 계산한 후 결과를 출력합니다.

이제 자바를 이용하여 다익스트라 알고리즘을 소스 코드로 구현하는 방법에 대해 알아보았습니다.

참고 자료

다익스트라 알고리즘 (위키피디아): https://ko.wikipedia.org/wiki/다익스트라_알고리즘