[개인 연습] 다익스트라 자바

자바 다익스트라 

- 한 점에서 다른 점까지의 간선 중에 최소값을 찾아나감

- bfs 이용

 

 

 

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

class Edge{
    int vertex;
    int weight;
    public Edge(int vertex, int weight) {
        this.vertex = vertex;
        this.weight = weight;
    }
}
public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] distance = new int[N + 1];
        Arrays.fill(distance, 99999999);
        ArrayList<Edge>[] adj = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            adj[i] = new ArrayList<Edge>();
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int V1 = Integer.parseInt(st.nextToken());
            int V2 = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            adj[V1].add(new Edge(V2, weight));
            adj[V2].add(new Edge(V1, weight));
        }
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int dest = Integer.parseInt(st.nextToken());
        distance[start] = 0;
        PriorityQueue<Edge> pq = new PriorityQueue<Edge>((a, b) -> b.weight - a.weight);
        pq.offer(new Edge(start, 0));
        while(!pq.isEmpty()) {
            Edge edge = pq.poll();
            for (int i = 0; i < adj[edge.vertex].size(); i++) {
                Edge tmp = adj[edge.vertex].get(i);
                if(distance[tmp.vertex] > d[edge.vertex] + tmp.weight) {
                    distance[tmp.vertex] = d[edge.vertex] + tmp.weight;
                    pq.add(new Edge(tmp.vertex, distance[tmp.vertex]));
                }
            }
        }
        for (int i = 1; i <= dest; i++) {
            System.out.println(distance[i]);
        }
        System.out.println(distance[dest]);
    }
}