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

다익스트라 (Dijkstra)

가중치가 존재하는 그래프의 시작 정점으로부터 다른 정점들까지의 최단 거리를 구하는 알고리즘

출발 노드로부터의 모든 노드의 최단 거리를 탐색한다.

제약 조건 : Edge의 가중치가 모두 양수일 때만 사용할 수 있다.

 

 

---

과정

 

 

 

그래프 구현

• 주로 인접 리스트를 사용하여 그래프를 구현한다. N의 크기가 클 경우를 대비하여 인접 리스트를 선택하는 편이 좋은 경우가 많다.

최단 거리 배열 초기화

• 최단 거리 배열(distance)을 초기화한다.
• 출발 노드는 0으로 설정하고, 다른 모든 노드는 무한대(INF)로 초기화한다.

가장 작은 값을 가진 노드 선택 및 최단 거리 배열 업데이트

1. 현재 방문하지 않은 노드 중 distance가 가장 작은 노드를 선택한다. 
2. 선택 노드의 최단 거리 배열 값 + 해당 노드에서 연결된 에지 가중치를 더한 값과 연결 노드의 현재 최단 거리 배열 값을 비교 -> 더 작은 값을 선택
   • min(선택 노드의 최단거리 배열 값 + 에지 가중치, 연결 노드의 최단 거리 배열의 값)

1. 현재 노드 1의 최단 거리가 0이고 노드 1에서 노드 2로 가는 에지의 가중치가 8이라면, 노드 2의 최단 거리 배열 값은 min(0 + 8, INF) = 8
2. 마찬가지로, 노드 1에서 노드 3으로 가는 에지의 가중치가 3이라면, 노드 3의 최단 거리 배열 값은 min(0 + 3, INF) = 3

방문 배열을 사용하여 반복

• 모든 노드가 선택될 때까지 위 과정을 반복한다. 방문 여부를 확인하는 visited 배열을 사용

 

<함께 보기> 그래프 구현하기 (인접 행렬, 인접 리스트)

https://sjh9708.tistory.com/221

[자료구조/JAVA] 그래프 이론 (Graph Theory)

 

 

 

 

 

 

---

Dijkstra 구현 : 백준 1753 (최단 경로)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// 노드를 표현하는 클래스, 우선순위 큐에서 가중치 기준으로 정렬하기 위해 Comparable 인터페이스 구현
class Node implements Comparable<Node> {
    int index;  // 노드의 인덱스
    int weight; // 해당 노드까지의 가중치

    // 생성자
    public Node(int index, int weight) {
        this.index = index;
        this.weight = weight;
    }

    // 우선순위 큐에서 사용될 비교 메서드 (가중치 기준 오름차순 정렬)
    @Override
    public int compareTo(Node n) {
        return this.weight - n.weight;
    }
}

public class Main {
    static int V; // 정점의 개수
    static int K; // 시작 정점
    static int E; // 간선의 개수
    static List<Node>[] graph; // 그래프를 표현하는 인접 리스트
    static int[] distance; // 최단 거리 배열
    static final int INF = 1000000; // 무한대를 나타내는 값

    // 다익스트라 알고리즘 구현
    static void dijkstra(int start) {
        // 방문 여부를 확인하는 배열
        boolean[] visited = new boolean[V + 1];

        // 최단 거리 배열을 무한대로 초기화 (시작 정점은 0으로 설정)
        Arrays.fill(distance, INF);
        distance[start] = 0;

        // 우선순위 큐 (최소 힙) 초기화
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.offer(new Node(start, 0));

        while (!queue.isEmpty()) {
            // 가장 최단 거리가 짧은 노드를 꺼내기
            Node edge = queue.poll();
            int u = edge.index;

            // 이미 방문한 노드는 무시
            if (!visited[u]) {
                visited[u] = true; // 노드 방문 처리

                // 현재 노드와 연결된 인접한 노드들 확인
                for (Node n : graph[u]) {
                    int v = n.index;
                    int weight = n.weight;

                    // 현재 노드를 거쳐 다른 노드로 가는 거리가 더 짧은 경우 최단 거리 배열 업데이트
                    if (!visited[v] && distance[u] + weight < distance[v]) {
                        distance[v] = distance[u] + weight;
                        queue.add(new Node(v, distance[v]));
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken()); // 정점의 개수 입력
        E = Integer.parseInt(st.nextToken()); // 간선의 개수 입력

        st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken()); // 시작 정점 입력

        // 그래프 초기화
        graph = new LinkedList[V + 1];
        distance = new int[V + 1];

        // 인접 리스트로 그래프 구현
        for (int i = 1; i <= V; i++) {
            graph[i] = new LinkedList<Node>();
        }

        // 간선 정보 입력
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph[u].add(new Node(v, w));
        }

        // 다익스트라 알고리즘 실행
        dijkstra(K);

        // 결과 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= V; i++) {
            if (distance[i] == INF) {
                sb.append("INF").append("\n");
            } else {
                sb.append(distance[i]).append("\n");
            }
        }

        System.out.println(sb);
    }
}

 

• Node : 노드의 인덱스와 해당 노드까지의 가중치를 저장. 우선순위 큐에서 가중치를 기준으로 정렬하기 위해 Comparable 인터페이스를 구현.
• 그래프 구현: 인접 리스트의 형태로 리스트(LinkedList<Node>)의 배열로 구현한다.
• 다익스트라 알고리즘
  • 최단 거리 배열 초기화 : 시작 정점은 0으로, 나머지는 INF로 초기화
  • 우선순위 큐 : 최소 거리를 가진 노드를 꺼내기 위해서 우선순위 큐 사용
  • 루프 반복 : 모든 정점을 방문할 때 까지 루프를 반복, 현재 큐에 있는 가장 거리가 짧은 노드를 꺼내 방문하지 않았을 경우 인접한 노드들의 최단 거리 업데이트

 

 

 

 

---

문제 : 백준 1504 (특정한 최단 경로)

 

• 특정 정점을 무조건 지나서 목적지 정점으로 이동하는 최단 거리를 구하는 문제이다.
• 지나야 하는 정점의 개수가 2개로 고정되어 있으므로 두 개의 케이스로 나누어 최소값을 계산한다.
  
  • [시작 -> 정점 V1] + [정점 V1 -> 정점 V2] + [정점 V2 -> 목적지]
  • [시작 -> 정점 V2] + [정점 V2 -> 정점 V1] + [정점 V1 -> 목적지]
• 정점과 간선을 중복해서 경유할 수 있으므로 시작점, 정점 V1, 정점 V2를 Start로 하는 다익스트라 계산을 각각 수행하여 위의 케이스 계산에 필요한 거리를 계산하면 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Node implements Comparable<Node>{
    int index;
    int weight;
    public Node(int index, int weight){
        this.index = index;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node n){
        return this.weight - n.weight;
    }
}

public class Main {
    static int V;
    static int E;
    static List<Node>[] graph;
    static int[] distance;
    static final int INF = 200000000;
    static void dijkstra(int start){
        boolean[] visited = new boolean[V+1];
        Arrays.fill(distance, INF);
        distance[start] = 0;
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.offer(new Node(start, 0));

        while(!queue.isEmpty()){
            Node edge = queue.poll();
            int u = edge.index;
            if(!visited[u]){
                visited[u] = true;
                for(Node n : graph[u]){
                    int v = n.index;
                    int weight = n.weight;
                    if (!visited[v] && distance[u] + weight < distance[v]) {
                        distance[v] = distance[u] + weight;
                        queue.add(new Node(v, distance[v]));
                    }
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        graph = new LinkedList[V + 1];
        distance = new int[V + 1];
        for(int i = 1; i <= V; i++){
            graph[i] = new LinkedList<Node>();
        }

        for(int i = 0; i < E; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            graph[u].add(new Node(v, w));
            graph[v].add(new Node(u, w));
        }

        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());

        dijkstra(1);
        int distStoV1 = distance[v1];
        int distStoV2 = distance[v2];

        dijkstra(v1);
        int distV1toV2 = distance[v2];
        int distV1toEnd = distance[V];

        dijkstra(v2);
        int distV2toEnd = distance[V];

        int result = Math.min((distStoV1 + distV1toV2 + distV2toEnd), (distStoV2 + distV1toV2 + distV1toEnd));
        if(result >= INF){
            result = -1;
        }
        System.out.println(result);

    }
}

•