다익스트라 (Dijkstra)

Dijkstra

• 시작정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
• 시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다.
• 탐욕 기법을 사용한 알고리즘으로 MST의 프림 알고리즘과 유사하다.
• 우선순위큐에 PQ에 있는 정점에서 해당정점까지의 거리가 가장 낮은 정점을 중심으로 거리 배열을 갱신하여 다시 큐에 넣는 행위를 반복하여 최종적으로 거리배열을 완성하는 알고리즘
• 음의 가중치를 허용하지 않는다.
• 정점 v까지 거리와 비교하여 더 짧아진 경우에 갱신합니다. 즉, dist[u] + w(u, v) = dist[v]로 갱신
• 시간 복잡도 : O(ElogV)

인접 리스트

백준 1753. 최단경로
https://www.acmicpc.net/problem/1753

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

/**
*  시간 : 852ms, 메모리 : 111,412KB
*/
class Node{
    int weight;
    int u;

    public Node(int weight, int u) {
        this.weight = weight;
        this.u = u;
    }
}
public class Main {
    static PriorityQueue<Node> priorityQueue = new PriorityQueue<>((o1, o2) -> {
        return o1.weight - o2.weight;
    });
    static List<Node>[] graph;
    static int[] dist;
    static int V, E, K;
    static int from, to, weight;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb;

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken());
        dist = new int[V+1];
        
        // 처음에 거리를 무한대 값으로 갱신
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        graph = new List[V+1];
        for (int i = 0; i < V+1; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());
            weight = Integer.parseInt(st.nextToken());
            graph[from].add(new Node(weight, to));
        }
        
        dijkstra(K);
        
        for (int i = 1; i <= V; i++) {
            if(dist[i] == Integer.MAX_VALUE) System.out.println("INF");
            else System.out.println(dist[i]);
        }
        br.close();
    }

    static void dijkstra(int start) {
    	// 시작지점의 값을 0으로 초기화
        dist[start] = 0;
        priorityQueue.offer(new Node(0, start));
        
        // "거리", "정점" 이 두가지의 인자를 가진 최소힙기반의 우선순위큐에 넣어가며 진행
        while (!priorityQueue.isEmpty()) {
            Node now = priorityQueue.poll();
            int here = now.u;
            int here_dist = now.weight;
            if(dist[here] != here_dist) continue;
            for (Node node : graph[here]) {
                int to = node.u;
                int weight = node.weight;
                if (dist[to] > dist[here] + weight) {
                    dist[to] = dist[here] + weight;
                    priorityQueue.offer(new Node(dist[to], to));
                }
            }
        }
    }
}

인접 행렬

백준 4485. 녹색 옷 입은 애가 젤다지?
https://www.acmicpc.net/problem/4485

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

/**
 *  시간 : 252ms, 메모리 : 21,744KB
 */
public class Main {
    static class Node implements Comparable<Node>{
        int y, x, weight;

        public Node(int y, int x, int weight) {
            this.y = y;
            this.x = x;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.weight, o.weight);
        }
    }
    static int N, cnt = 1;
    static int[][] map;
    static boolean[][] visited;
    static int[][] dist;
    static int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    static PriorityQueue<Node> pq;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb;

        while (true){
            N = Integer.parseInt(br.readLine());
            if(N == 0) System.exit(0);
            map = new int[N][N];
            visited = new boolean[N][N];

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            dijkstra();

            sb = new StringBuilder();
            sb.append("Problem").append(" ").append(cnt++).append(":").append(" ").append(dist[N-1][N-1]);
            System.out.println(sb.toString());
        }
    }
    static void dijkstra(){
        dist = new int[N][N];
        for (int i = 0; i < N; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        dist[0][0] = map[0][0];
        pq = new PriorityQueue<>();
        pq.offer(new Node(0, 0, dist[0][0]));
        while (!pq.isEmpty()){
            Node now = pq.poll();
            int y = now.y;
            int x = now.x;
            int weight = now.weight;
            if(y == N-1 && x == N-1) break;
            if(dist[y][x] != weight) continue;
            visited[y][x] = true;
            for (int i = 0; i < 4; i++) {
                int ny = y + dir[i][0];
                int nx = x + dir[i][1];
                if(ny < 0 || ny >= N || nx < 0 || nx >= N || visited[ny][nx]) continue;
                if(dist[ny][nx] > map[ny][nx] + weight){
                    dist[ny][nx] = map[ny][nx] + weight;
                    pq.offer(new Node(ny, nx, dist[ny][nx]));
                }
            }
        }
    }
}