[Java] 다익스트로 알고리즘 & 플로이드 와샬 알고리즘

다익스트라 알고리즘(Dijkstra Algorithm)

3학년 1학기 Computer Network 강의에서 처음 접하게 되었다. 이 알고리즘은 다이나믹 프로그래밍을 활용하여 하나의 정점에서 다른 모든 정점까지의 최단 경로를 구할때 사용한 알고리즘이였다.

코딩 테스트에서는 위에서 말했듯이 정점간의 가중치가 있을 때 하나의 특정 정점에서 다른 모든 정점까지의 최단 경로를 구할때 사용할 수 있다.

자바 코드

import java.util.*;

public class Dijkstra {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 노드 개수
        int M = sc.nextInt(); // 간선 개수

        List<List<int[]>> edge = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            edge.add(new ArrayList<>());
        }

        // 간선 입력
        for (int i = 0; i < M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();

            // 단방향일 경우
            edge.get(a).add(new int[]{c, b});
            // 양방향일 경우
            edge.get(b).add(new int[]{c, a});
        }

        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE); // 무한대로 초기화

        // 시작점 설정
        dist[1] = 0;
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(o -> o[0]));
        heap.offer(new int[]{0, 1}); // 비용, 노드

        while (!heap.isEmpty()) {
            int[] current = heap.poll();
            int w = current[0]; // 현재 비용
            int v = current[1]; // 현재 노드

            // 현재 비용이 저장된 거리와 다르면 건너뜀
            if (w > dist[v]) continue;

            for (int[] next : edge.get(v)) {
                int nw = next[0]; // 다음 노드로의 비용
                int nv = next[1]; // 다음 노드

                // 더 짧은 경로가 발견되면 갱신
                if (dist[nv] > dist[v] + nw) {
                    dist[nv] = dist[v] + nw;
                    heap.offer(new int[]{dist[nv], nv});
                }
            }
        }

        // 결과 출력 (1번 노드부터 거리 출력)
        for (int i = 1; i <= N; i++) {
            System.out.println("Node " + i + ": " + (dist[i] == Integer.MAX_VALUE ? "INF" : dist[i]));
        }
    }
}

이 다익스트라는 우선순위 큐(heapq)를 통해 구현됐다.

전체적인 코드의 흐름을 보면 그래프 정보를 단방향인지 양방향인지 잘 확인하여 인접 리스트 형식으로 변환해 준다.
거리 정보를 담는 리스트(모두 무한대로 초기화)에서 시작 노드의 거리 정보는 시작지점이기 때문에 0으로 바꿔준다. 그런 다음 우선순위 큐에 (비용,시작노드)를 담고 이 우선순위 큐가 비기 전까지 while문을 돌리기 시작한다.
우선순위 큐에서 heappop을 하게되면 비용을 기준으로 정렬되기 때문에 비용이 heap내에서 비용이 가장작은 튜플이 반환되며 w에는 해당 비용, v는 해당 노드 번호가 담기게 된다.
현재 처리하려는 노드와 비용이 최신 정보인지 확인하여 최신이라면 현재 노드를 무시한다.
만약 최신 정보가 아니라면 인접 리스트에서 인접한 노드로의 비용과 노드를 변수 nw, nv에 담고 인접 노드 nv까지의 현재 저장된 거리보다 현재 처리 중인 노드 v에다가 인접 노드까지의 비용 nw를 더한 것이 더 작다면 최단 거리라는 것이기 때문에 dist[nv] = dist[v] + nw로 바꿔주고 heap에다가 해당 인접 노드까지의 갱신된 거리와 노드 번호를 heappush해주는 것을 반복한다.
이렇게 되면 결국 거리 리스트가 모두 갱신될텐데 필요한 값을 쓰면 된다.

if w != dist[v]: continue의 존재 이유?
if w != dist[v]: continue라는 코드는 현재 처리하려는 노드와 비용이 최신 정보인지를 확인하는 용도로 존재합니다.
다익스트라 알고리즘을 수행하는 과정에서, 어떤 노드를 방문할 때마다 그 노드를 통해 갈 수 있는 다른 노드들의 거리 정보를 업데이트하고, 그 정보를 우선순위 큐에 넣습니다. 그런데 이 때문에 우선순위 큐에는 같은 노드에 대한 정보가 여러 번 들어갈 수 있습니다.
이런 상황에서, 우선순위 큐에서 노드를 꺼내 처리할 때, 그 노드에 대한 거리 정보가 최신인지 아닌지를 확인하지 않으면, 오래된 거리 정보에 따라 불필요한 계산을 반복하게 될 수 있습니다.
따라서 if w != dist[v]: continue는 현재 처리하려는 노드의 거리 정보가 최신이 아니라면(즉, 이미 더 짧은 거리로 해당 노드를 방문했다면), 그 노드를 무시하고 다음 노드를 처리하도록 하는 역할을 합니다. 이를 통해 불필요한 계산을 줄이고 알고리즘의 효율성을 높이는 역할을 합니다.

 

 

---

이전 글에서 하나의 노드(시작점)에서 다른 모든 노드까지의 비용을 구할 수 있어 최단 거리 문제에서 쓸 수 있다는 것을 알 수 있다.
이번 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)는 모든 노드에서 모든 노드로 가는 최단 거리를 알아낼 수 있다. 이 알고리즘에 대해서 알아보자!

모든 노드에서 모든 노드로 갈때의 최단 거리!!

왜 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)을 써야하나?

처음 이 알고리즘은 모든 노드에서 모든 노드까지의 최단 거리를 구할때 사용한다는 것을 듣고 다익스트라를 통해서 하나의 노드에서 최단거리를 각각 구하는 것을 모든 노드에 대해서 반복문을 통해서 충분히 구할 수 있는거 아닌가? 라는 생각이 들었다.
알아보니 내 생각이 맞았다. 어쩌면 당연한거다. 그런데 굳이 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)을 사용하는 이유는 시간 복잡도 때문이다. 다익스트라 알고리즘보다 시간 복잡도를 감소시킬 수 있다.

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 구현

작동원리

• 노드 i에서 노드 j로 가는 각각의 비용 리스트 선언하기, 초기값은 INF
• 각 간선의 비용들을 비용 리스트에 반영
• 모든 노드에 대해 해당 노드를 거쳐서 갈때 비용이 낮아질 경우 값 갱신

import java.util.*;

public class FloydWarshall {
    static final int INF = (int) 1e9; // 무한대를 나타내는 값

    public static int solution(int n, int s, int a, int b, int[][] fares) {
        int[][] dist = new int[n + 1][n + 1];

        // 거리 배열 초기화
        for (int i = 1; i <= n; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0; // 자기 자신으로 가는 비용은 0
        }

        // 간선 정보 입력
        for (int[] fare : fares) {
            int row = fare[0];
            int col = fare[1];
            int cost = fare[2];

            dist[row][col] = Math.min(dist[row][col], cost);
            dist[col][row] = Math.min(dist[col][row], cost); // 양방향 처리
        }

        // 플로이드-워셜 알고리즘
        for (int k = 1; k <= n; k++) { // 거치는 점
            for (int i = 1; i <= n; i++) { // 시작점
                for (int j = 1; j <= n; j++) { // 도착점
                    if (dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        // 최소 비용 계산
        int answer = INF;
        for (int t = 1; t <= n; t++) {
            // s -> t, t -> a, t -> b 의 최소 비용을 더함
            answer = Math.min(answer, dist[s][t] + dist[t][a] + dist[t][b]);
        }

        return answer;
    }

    public static void main(String[] args) {
        int n = 6; // 노드 개수
        int s = 4; // 출발점
        int a = 6; // A의 도착점
        int b = 2; // B의 도착점
        int[][] fares = {
            {4, 1, 10}, {3, 5, 24}, {5, 6, 2}, {3, 1, 41},
            {5, 1, 24}, {4, 6, 50}, {2, 4, 66}, {2, 3, 22},
            {1, 6, 25}
        };

        System.out.println("최소 비용: " + solution(n, s, a, b, fares));
    }
}