다익스트라(Dijkstra) 알고리즘

다익스트라 알고리즘

• 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘
• 음의 가중치X
• 시간 복잡도 O((V+E)logV) V=정점 개수, E=한 정점의 주변노드

 

예시

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
 
 
public class Main{
    
    public static class Node{
        int v,w;
 
        public Node(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }
    static List<Node> list[];
    static int [] distance;
    static boolean []visited;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        
        list =new ArrayList[N+1];
        distance = new int [N+1];
        visited = new boolean[N+1];
        
        for(int i=1;i<N+1;i++) list[i]= new ArrayList<>();
        
        for(int i=0;i<M;i++) {
            st = new StringTokenizer(br.readLine()," ");
            int start = Integer.parseInt(st.nextToken());
            int arrive = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());
            list[start].add(new Node(arrive,price));
        }
        
        st = new StringTokenizer(br.readLine()," ");
        int go = Integer.parseInt(st.nextToken()); //시작점
        int end = Integer.parseInt(st.nextToken()); //도착점
        
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[go] = 0; //시작점 0으로
        
        int min, current = 0;
        for(int i=0; i<N;i++) {
            min = Integer.MAX_VALUE;
            current = -1;
            for(int j=1;j<N+1;j++) { //거리가 가장짧은 정점찾기
                if(!visited[j] && distance[j]<min) {
                    min = distance[j];
                    current =j;
                }
            }
            if(current == end) break;
            
            for(Node next : list[current]) { //찾은 정점과 연결된 정점들의 거리 저장
                if(!visited[next.v] && distance[next.v]> distance[current]+next.w) {
                    distance[next.v] = distance[current] + next.w;
                }
            }
            visited[current] = true;
        }
        System.out.println(distance[end]);
    }
}