[알고리즘] 다익스트라 (그래프 최단 경로)

그래프에서 최단 경로란?

특정 A 노드에서 B 노드로 이동하려할때 A에서 B로가는 여러가지의 경로가 존재 한다면 그중에서 거리가 가장 짧은 경로를 최단 경로라고 한다.

그래프에서 거리가 짧다는 것은 간선에 가중치가 없다면 간선이 최소인 경로, 가중치가 있다면 그래프에 음수 사이클이 없을 경우 경로의 가중치의 합이 최소를 의미한다.

 

다익스트라

• 특정 정점에서 갈 수 있는 모든 정점들까지의 최단 경로를 구하는 알고리즘
• 우선순위 큐를 사용
• 가중치가 음수인 간선이 없는 가중 그래프에서 사용
• O(ElogV)

 

알고리즘 과정

1. 출발 노드의 거리를 0으로 설정하고, 다른 모든 노드의 거리를 무한대(∞)로 초기화한다.
2. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 찾아서 그 중 거리가 가장 짧은 노드를 선택하고 그 노드를 방문 처리한다.
3. 해당 노드를 거쳐 다른 노드로 넘어가는 경로의 가중치를 계산해 원래보다 더 작으면 최단 거리 테이블을 업데이트한다.
4. 모든 노드가 처리될 때까지 2~3의 과정을 반복한다.

 

다익스트라 알고리즘 과정 예시

 

코드

 

import java.util.*;

class Dijkstra {
    static class Edge {
        int to, weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static int[] dijkstra(int n, List<List<Edge>> graph, int start) {
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        int[] distances = new int[n];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[start] = 0;

        pq.add(new Edge(start, 0));

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

            for (Edge edge : graph.get(current.to)) {
                int newDist = distances[current.to] + edge.weight;
                if (newDist < distances[edge.to]) {
                    distances[edge.to] = newDist;
                    pq.add(new Edge(edge.to, newDist));
                }
            }
        }
        return distances;
    }

    public static void main(String[] args) {
        int n = 5;
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        graph.get(0).add(new Edge(1, 2));
        graph.get(0).add(new Edge(2, 4));
        graph.get(1).add(new Edge(2, 1));
        graph.get(1).add(new Edge(3, 7));
        graph.get(2).add(new Edge(3, 3));
        graph.get(3).add(new Edge(4, 1));

        int[] distances = dijkstra(n, graph, 0);
        System.out.println("노드 0과의 거리: " + Arrays.toString(distances));
    }
}