[GDG 스터디] 다익스트라를 이용하여 모든 노드에 대한 최단 경로 구하기

다익스트라 알고리즘

다익스트라(Dijkstra) ?

• 다익스트라 알고리즘은 그래프에서 한 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘 중 하나이다.
• 해당 노드까지의 최단 경로를 찾는 과정에서 다른 모든 정점까지의 경로값도 계산해주면서 각 정점까지의 최단 경로도 모두 찾게 된다 !
• 가중치가 양수일 때만 사용 가능하다 !

---

💡 다익스트라 핵심 개념 - Greedy

• 다익스트라는 그리디(Greedy) 알고리즘의 일종으로, 매 단계마다 **가장 최적의 선택(현재 최단 거리를 가진 정점)**을 한다. → 즉, 아직 방문하지 않은 정점 중에서 최단 거리의 정점을 선택해 탐색한다.

<aside> 💡

방문 여부도 체크해야 하나 ?

• 따로 체크할 필요가 없다 ! → 노드는 한 번 방문했을 때 최단 거리값으로 갱신되기 때문에, 아래처럼 거리를 갱신하는 조건문에 걸리지 않아 우선순위 큐에 이후 방문할 노드로 추가될 일이 없다 !

if (newDist < distances[neighbor]) {
		distances[neighbor] = newDist;
		pq.add(new Edge(neighbor, newDist));
}

</aside>

---

💡 다익스트라 핵심 개념 - 최단 거리 테이블

• 다익스트라 알고리즘의 최단거리 테이블은 특정 시작 정점에서 모든 다른 정점까지의 최단 거리를 기록하는 테이블이다. → 다익스트라 알고리즘이 실행되는 동안 최단 거리를 점진적으로 갱신하면서 경로를 탐색할 때 사용된다.

최단 거리 테이블의 구성과 갱신 과정

1. 초기화
   1. 시작 정점에서의 거리는 0으로 설정한다.
   2. 나머지 모든 정점은 아직 방문되지 않았으므로 거리를 무한대(∞; INF)로 설정한다.
2. 탐색 과정
   1. 현재 테이블에 있는 최단 거리가 가장 작은 정점을 선택하여 해당 정점을 방문 처리한다.
   2. 선택된 정점을 기준으로 인접한 정점들을 확인하며, 최단 거리 테이블을 갱신한다.
   3. 이 과정을 모든 정점을 방문할 때까지 반복한다.
3. 결과
   1. 시작 정점에서 모든 정점까지의 최단 거리를 나타내게 된다.

---

💡 다익스트라 핵심 개념 - 시간 복잡도 & Heap

• 다익스트라 알고리즘에서 최단 거리를 찾기 위해 선형 검색을 해버리면 시간 복잡도는 O(V^2)가 돼버린다. → 모든 정점에 대해 최단 거리를 갱신하는 과정에서 비효율적인 검색이 발생한다.

<aside> 💡

힙(Heap) 자료구조를 사용하는 이유 !

• 다익스트라 알고리즘에서는 “현재까지 가장 작은 거리”를 가진 정점을 빠르게 선택해야 하기 때문에, 이 과정에서 효율적으로 탐색을 하기 위해 우선순위 큐가 필요한 것이다 ! → 이런 우선순위 큐의 삽입 및 최소값 추출을 효율적으로 할 수 있도록 설계되어 있는 것이 힙 자료구조이다. ( ex: 이진 힙 → 삽입 및 삭제 연산이 O(log V)의 시간 복잡도를 가진다. )
• 우선순위 큐를 구현할 때 힙(Heap) 자료구조를 사용하면 시간 복잡도를 크게 줄일 수 있다. → 주로 이진 힙(Binary Heap)이나 피보나치 힙(Fibonacci Heap)이 사용된다.
• 힙을 사용한 구현에서 시간 복잡도는 O(E * log V)이다. </aside>

---

💡 다익스트라 핵심 개념 - Priority Queue

• 우선순위 큐(Priority Queue)를 통해 현재 최단 거리를 가진 정점을 빠르게 선택할 수 있다. → **PriorityQueue**는 내부적으로 이진 힙(Binary Heap)을 기반으로 동작한다 !

import java.util.*;

class Graph {
    static class Edge {
        int target, weight;
        Edge(int target, int weight) {
            this.target = target;
            this.weight = weight;
        }
    }

    private final List<List<Edge>> adjList;

    Graph(int nodes) {
        adjList = new ArrayList<>();
        for (int i = 0; i < nodes; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    void addEdge(int source, int target, int weight) {
        adjList.get(source).add(new Edge(target, weight));
        adjList.get(target).add(new Edge(source, weight)); // For undirected graph
    }

    void dijkstra(int start) {
        int nodes = adjList.size();
        int[] distances = new int[nodes];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[start] = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        pq.add(new Edge(start, 0));

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

            for (Edge edge : adjList.get(currentNode)) {
                int neighbor = edge.target;
                int newDist = distances[currentNode] + edge.weight;

                if (newDist < distances[neighbor]) {
                    distances[neighbor] = newDist;
                    pq.add(new Edge(neighbor, newDist));
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(0, 1, 4);
        graph.addEdge(0, 2, 2);
        graph.addEdge(1, 2, 5);
        graph.addEdge(1, 3, 10);
        graph.addEdge(2, 4, 3);
        graph.addEdge(4, 3, 4);
        graph.addEdge(3, 5, 11);

        graph.dijkstra(0);
    }
}

---

문제: 최단경로 (백준 1753)

문제 링크

 

---

알고리즘 [접근 방법]

• 다익스트라 알고리즘을 이용해서 시작 정점으로부터 각 정점들의 최단 경로를 구해준다.

---

해결 코드

• 우선순위 큐에 자료가 삽입되고 추출될 때, 거리값이 작은 값이 높은 우선순위에 배정되도록 재정의해줬다.
• 현재 방문한 노드와 인접한 노드들을 탐색하고, 최단 거리 테이블(distances 배열)을 기반으로 시작 노드로부터 해당 노드들까지의 거리를 더 작은 값으로 갱신해주는 과정을 반복한 것이다. → 방문 순서는 현재 노드에서 거리값이 가장 작은 노드들 먼저 방문(우선순위 큐 pr에서 추출)한다.

import java.util.*;
import java.io.*;

public class Main {
    
    static final int INF = Integer.MAX_VALUE;
    
    static int V, E, K;
    static int[] distances;
    static ArrayList<Node>[] graph;
    static boolean[] visited;
    
    static class Node implements Comparable<Node> {
        int end;
        int distance;
        
        public Node(int end, int distance) {
            this.end = end;
            this.distance = distance;
        }
        
        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.distance, other.distance);
        }
    }
    
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        V = Integer.parseInt(st.nextToken()); // 정점 개수
        E = Integer.parseInt(st.nextToken()); // 간선 개수
        K = Integer.parseInt(br.readLine()); // 시작 노드
        
        visited = new boolean[V + 1];
        distances = new int[V + 1];
        graph = new ArrayList[V + 1];
        
        for (int i = 1; i <= V; ++i) {
            distances[i] = INF;
            graph[i] = new ArrayList<>();
        }
        
        for (int i = 1; i <= E; ++i) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int distance = Integer.parseInt(st.nextToken());
            
            graph[start].add(new Node(end, distance));
        }
        
        dijkstra();
        
        for (int i = 1; i <= V; ++i) {
            System.out.println(distances[i] == INF ? "INF" : distances[i]);
        }
        
    }
    
    private static void dijkstra() {
        distances[K] = 0;
        PriorityQueue<Node> queue = new PriorityQueue<>();
        // PriorityQueue<Node> queue = new PriorityQueue<>((a, b) -> Integer.compare(a.distance, b.distance));
        queue.add(new Node(K, 0));
        
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            int curNode = cur.end;
            int curDistance = cur.distance;
            
            // 처음 노드에서 해당 노드까지의 거리가 갱신될 필요없는 경우
            if (curDistance > distances[curNode]) {
                continue;
            }
            
            // 현재 정점과 연결된 모든 정점을 탐색
            for (Node node : graph[curNode]) {
                int newNode = node.end;
                int newDistance = curDistance + node.distance;  // 새로운 거리 계산
                
                // 새로 계산한 거리가 기존 거리보다 작으면 거리 갱신
                if (newDistance < distances[newNode]) {
                    distances[newNode] = newDistance;
                    queue.add(new Node(newNode, newDistance));  // 갱신된 거리를 큐에 추가
                }
            }
        }
    }
    
}

---

정리

• 다익스트라 알고리즘은 이진 힙으로 구현된 우선순위 큐를 기반으로 동작하는 알고리즘으로, 가중치가 양수인 (무)방향 그래프에서 사용해야 한다 !

 

https://thin-azimuth-2a9.notion.site/GDG-144f4ee21c008026a35cc4203db63fa1?pvs=4