동블

그래프 뷰

07. 그래프-최단경로

6 min read

그래프 - 최단경로

Summary

최단경로는 가중치 종류로 알고리즘을 고른다.
음수 없음이면 Dijkstra, 0/1 비용이면 0-1 BFS, 음수 간선이면 Bellman-Ford다.

선택 기준

상황알고리즘
가중치 없음BFS
가중치 0 또는 10-1 BFS
가중치 있음, 음수 없음Dijkstra
음수 간선 있음Bellman-Ford
모든 정점 쌍 최단거리Floyd-Warshall

Dijkstra long 검증 템플릿

Warning

거리/비용 합은 int가 넘을 수 있으므로 기본은 long으로 둔다.

import java.io.*;
import java.util.*;
 
public class Main {
    static class Edge {
        int to;
        long cost;
 
        Edge(int to, long cost) {
            this.to = to;
            this.cost = cost;
        }
    }
 
    static final long INF = Long.MAX_VALUE / 4;
    static int v, e, start;
    static List<Edge>[] graph;
    static long[] dist;
 
    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());
        start = Integer.parseInt(st.nextToken());
 
        graph = new ArrayList[v + 1];
        for (int i = 1; i <= v; i++) {
            graph[i] = new ArrayList<>();
        }
 
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            long cost = Long.parseLong(st.nextToken());
            graph[from].add(new Edge(to, cost));
        }
 
        dijkstra(start);
 
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= v; i++) {
            sb.append(dist[i] == INF ? "INF" : dist[i]).append('\n');
        }
        System.out.print(sb);
    }
 
    static void dijkstra(int start) {
        dist = new long[v + 1];
        Arrays.fill(dist, INF);
 
        PriorityQueue<Edge> pq = new PriorityQueue<>((a, b) -> Long.compare(a.cost, b.cost));
        dist[start] = 0;
        pq.offer(new Edge(start, 0));
 
        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
 
            if (dist[cur.to] < cur.cost) continue;
 
            for (Edge next : graph[cur.to]) {
                long newCost = cur.cost + next.cost;
 
                if (newCost < dist[next.to]) {
                    dist[next.to] = newCost;
                    pq.offer(new Edge(next.to, newCost));
                }
            }
        }
    }
}

0-1 BFS 검증 템플릿

import java.io.*;
import java.util.*;
 
public class Main {
    static final int INF = 1_000_000_000;
    static int n, m;
    static char[][] board;
    static int[][] dist;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
 
        board = new char[n][m];
        dist = new int[n][m];
 
        for (int i = 0; i < n; i++) {
            board[i] = br.readLine().toCharArray();
            Arrays.fill(dist[i], INF);
        }
 
        zeroOneBfs(0, 0);
        System.out.println(dist[n - 1][m - 1]);
    }
 
    static void zeroOneBfs(int sx, int sy) {
        Deque<int[]> dq = new ArrayDeque<>();
        dq.offerFirst(new int[]{sx, sy});
        dist[sx][sy] = 0;
 
        while (!dq.isEmpty()) {
            int[] cur = dq.pollFirst();
            int x = cur[0];
            int y = cur[1];
 
            for (int dir = 0; dir < 4; dir++) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];
 
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
 
                int weight = board[nx][ny] - '0'; // 이동 비용이 0 또는 1
                if (dist[nx][ny] <= dist[x][y] + weight) continue;
 
                dist[nx][ny] = dist[x][y] + weight;
                if (weight == 0) dq.offerFirst(new int[]{nx, ny});
                else dq.offerLast(new int[]{nx, ny});
            }
        }
    }
}

Bellman-Ford 검증 템플릿

import java.io.*;
import java.util.*;
 
public class Main {
    static class Edge {
        int from, to;
        long cost;
 
        Edge(int from, int to, long cost) {
            this.from = from;
            this.to = to;
            this.cost = cost;
        }
    }
 
    static final long INF = Long.MAX_VALUE / 4;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());
 
        Edge[] edges = new Edge[e];
        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            long cost = Long.parseLong(st.nextToken());
            edges[i] = new Edge(from, to, cost);
        }
 
        long[] dist = new long[v + 1];
        Arrays.fill(dist, INF);
        dist[start] = 0;
 
        boolean updated = false;
        for (int i = 1; i <= v; i++) {
            updated = false;
            for (Edge edge : edges) {
                if (dist[edge.from] == INF) continue;
                if (dist[edge.to] > dist[edge.from] + edge.cost) {
                    dist[edge.to] = dist[edge.from] + edge.cost;
                    updated = true;
                    if (i == v) {
                        System.out.println("NEGATIVE CYCLE");
                        return;
                    }
                }
            }
            if (!updated) break;
        }
 
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= v; i++) {
            sb.append(dist[i] == INF ? "INF" : dist[i]).append('\n');
        }
        System.out.print(sb);
    }
}

Floyd-Warshall 검증 템플릿

Warning

INF + INF를 더하지 않도록 guard를 둔다.
중복 간선은 더 작은 비용만 남긴다.

import java.io.*;
import java.util.*;
 
public class Main {
    static final long INF = Long.MAX_VALUE / 4;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
 
        long[][] dist = new long[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0;
        }
 
        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            long cost = Long.parseLong(st.nextToken());
            dist[from][to] = Math.min(dist[from][to], cost); // 중복 간선 처리
        }
 
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                if (dist[i][k] == INF) continue;
                for (int j = 1; j <= n; j++) {
                    if (dist[k][j] == INF) continue;
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
 
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                sb.append(dist[i][j] == INF ? 0 : dist[i][j]);
                if (j < n) sb.append(' ');
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }
}

엣지케이스

도달 불가능한 노드
시작 == 도착
중복 간선
자기 루프
비용 합 int overflow
음수 간선 존재 여부
Floyd에서 INF guard

백지 복원

1. Dijkstra를 쓰면 안 되는 조건은?
2. 0-1 BFS에서 비용 0 간선은 deque 어디에 넣는가?
3. Bellman-Ford에서 음수 사이클은 몇 번째 반복에서 확인하는가?
4. Floyd의 시간복잡도는?

관련 문서