[정리] 다익스트라

BAMDAL.Dev·2022년 6월 26일
0

정리

목록 보기
9/11

다익스트라

  • 다이나믹 프로그래밍을 활용한 최단 경로 탐색 알고리즘이다.
  • 단 음의 간선을 포함 할 수 없다.
  • 현실 세계에 사용하기 적합한 알고리즘이다.

문제와 코드를 통해서 알아보겠다

  • 백준 (15649번) N과 M(1)

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

풀이

package Dijkstra;

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

public class ShortWay {

    static class Node{
        int idx;
        int cost;

        public Node(int idx, int cost){
            this.idx = idx;
            this.cost = cost;
        }
    }
//    다익스트라 (모든)!! 최단 경로 구할시 사용
    static void dijstra(int start){
        Queue<Node> q = new PriorityQueue<>((o1, o2) -> o1.cost-o2.cost);
//        초기화
        q.offer(new Node(start,0));

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

            for(int i = 0;i< list.get(no.idx).size();i++){
                Node nx = list.get(no.idx).get(i);
                if(dist[nx.idx] > no.cost + nx.cost){
                    dist[nx.idx] = no.cost + nx.cost;
                    q.offer(new Node(nx.idx,dist[nx.idx]));
                }
            }
        }
    }

    static int[] dist;
    static List<List<Node>> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        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());
        dist = new int[v+1];

        st = new StringTokenizer(br.readLine()," ");
        int s = Integer.parseInt(st.nextToken());
//      초기화
        for(int i = 0;i<=v;i++){
            list.add(new ArrayList<Node>());
            dist[i] = Integer.MAX_VALUE;
        }

        for(int i = 0;i<e;i++){
            st = new StringTokenizer(br.readLine()," ");
            int u = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            list.get(u).add(new Node(V,w));
        }
        dist[s] = 0;
        dijstra(s);

        for(int i = 1;i<=v;i++){
            if(dist[i] == Integer.MAX_VALUE)
                System.out.println("INF");
            else
                System.out.println(dist[i]);
        }
    }
}
profile
궁금증을 가지며 코딩하는 개발JA 주니어🐻

0개의 댓글