최단 경로 알고리즘

잡소리

문제를 잘 푸는 건 아니지만 BFS, DFS, Brute-force, DP, Greedy, 구현 등 여러 알고리즘을 어느 정도 이해하고 있다는 생각이 들었다. 그런데 문제를 풀다보면 왕왕 등장해서 나를 당황시켰던 알고리즘이 바로 최단 경로 알고리즘이다. 마주치면 그냥 모른 척 지나갔는데 항상 찜찜했다.
찜찜한 마음에 친구에게 물어보면 맨날 이런 식이었다.

나: 다익스트라가 뭐예요?
친구: 최단경로 찾는 거요
나: ..? (어쩔티비)

그래서 최단 경로를 제대로 알고 나면 후련할 것 같아서 정리한다.
이번 기회에 깊이 공부해보자!

가중치가 있는 경우 최단 경로를 구하는 알고리즘에는 대표적으로 두 가지가 있다.
임의의 정점에서 모든 정점까지의 최단경로를 구하는 다익스트라 (제일 유명)
모든 정점에서 다른 모든 정점까지의 최단경로를 구하는 플로이드-워셜
이외에도 벨만-포드가 있다는데 이건 나중에 기회되면 해보는 걸로

다익스트라

• 음이 아닌 간선을 가진 그래프에서 특정 정점에서 모든 정점까지의 최단 경로를 구하는 알고리즘
• 그리디 알고리즘으로 분류 (매 상황에서 가장 비용이 적은 노드를 선택)
• 이미 방문 처리된 노드는 최단 거리가 결정된 것임
• 한 단계당 하나의 노드에 대한 최단 거리 값을 확실히 찾는 것으로 이해
• 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 heap과 우선순위 큐를 사용하여 구현
• heap을 이용한 다익스트라 알고리즘 시간복잡도는 O(ElogV)

동작과정

1. 출발 노드를 설정
2. 최단 거리 테이블을 초기화(자기 자신까지의 거리는 0, 도달하지 못하는 정점은 무한)
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 (선택된 노드까지의 최단거리는 바뀌지 않음 다른 노드를 거쳐 오면 무조건 거리가 더 크기 때문에)
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
5. 위 3번 4번 과정을 반복

우선순위큐

• 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Dijkstra {
    static int v, e, start;
    static int[] dist;
    static ArrayList<ArrayList<Node>> graph;

    static class Node {
        int idx;
        int cost;
        Node(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }
    }

    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());
        start = Integer.parseInt(br.readLine());
        dist = new int[v + 1];
        graph = new ArrayList<>();
        for(int i = 0; i < v+1; i++) {
            graph.add(new ArrayList<>());
        }

        for(int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            graph.get(a).add(new Node(b, c));
        }

        for(int i = 0; i < v+1; i++) {
            dist[i] = Integer.MAX_VALUE;
        }

        PriorityQueue<Node> q = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.cost, o2.cost));
        q.offer(new Node(start, 0));
        dist[start] = 0;

        while (!q.isEmpty()) {
            Node curNode = q.poll();
            if(dist[curNode.idx] < curNode.cost) continue;

            for(int i = 0; i < graph.get(curNode.idx).size(); i++) {
                Node nNode = graph.get(curNode.idx).get(i);
                if(curNode.cost + nNode.cost < dist[nNode.idx]) {
                    dist[nNode.idx] = curNode.cost + nNode.cost;
                    q.offer(new Node(nNode.idx, dist[nNode.idx]));
                }
            }
        }
        System.out.println(Arrays.toString(dist));
    }
}

플로이드 워셜

• 모든 노드에서 다른 모든 노드까지의 최단 경로를 구하는 알고리즘
• 2차원 테이블에 최단 거리 정보를 저장하는 다이나믹 프로그래밍 유형
• 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인
• 점화식 : min(Dab , Dak + Dkb)
• 플로이드 워셜의 시간복잡도는 O(V^3)

동작과정

1. 최단거리 테이블 초기화 (현재 노드 -> 현재노드 : 0, 나머지는 무한)
2. 점화식에 맞게 테이블 갱신

코드

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

public class Floydwarshall {

    static int n, m;
    static int[][] dist;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        dist = new int[n][n];
        // 테이블 초기화
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i == j) {
                    dist[i][j] = 0;
                    continue;
                }
                dist[i][j] = 1000000000;
            }
        }

        // 간선 거리 저장
        for(int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            dist[a][b] = Math.min(dist[a][b], d);
            dist[b][a] = Math.min(dist[b][a], d);
        }

        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }

        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++) {
                System.out.print(dist[i][j] + " ");
            }
            System.out.println("");
        }
    }
}