최단 경로 알고리즘(다익스트라)

다익스트라

• 촐발점에서 목표점까지의 최단 경로를 구하는 알고리즘
• 한 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있음
• 간선에 음의 가중치가 없어야 함
• 그리디 + DP형태
• 알고리즘복잡도 : O(ElogV)

순서

• 인접 리스트로 그래프를 나타낸다.
• 최단 거리 배열을 초기화한다
  • 출발 노드는 거리가 없으므로 0으로 초기화를 한다.
  • 나머지 노드는 INF로 초기화를 한다.
• 값이 가장 작은 노드를 선택한다
• 배열을 갱신한다.
  • 선택한 노드의 간선의 값으로 다른 노드의 거리 값을 갱신한다.

백준1753

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static ArrayList<Node>[] A;
    static boolean[] visited;
    static int[] distance;
    static int V;
    static int E;

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        V = input.nextInt();
        E = input.nextInt();
        int startPoint = input.nextInt();

        visited = new boolean[V+1];
        distance = new int[V+1];
        for(int i=1; i<=V; i++){
            distance[i] = Integer.MAX_VALUE;
        }
        distance[startPoint] = 0;

        A = new ArrayList[V + 1];
        for (int i = 0; i < V + 1; i++) {
            A[i] = new ArrayList<>();
        }

        for (int i = 0; i < E; i++) {
            int start = input.nextInt();
            int end = input.nextInt();
            int add = input.nextInt();
            A[start].add(new Node(end, add));
        }

        findShort();

       for(int i=1; i<=V; i++){
           if(distance[i] == Integer.MAX_VALUE){
               System.out.println("INF");
           }else{
               System.out.println(distance[i]);
           }
       }
    }
    public static void findShort() {
        for(int i=1; i<=V; i++){
            int startPoint = findMin();
            visited[startPoint] = true;
            for(Node node : A[startPoint]){
                if(distance[startPoint] + node.add < distance[node.end]){
                    distance[node.end] = distance[startPoint] + node.add;
                }
            }
        }
    }

    public static int findMin(){
        int min = Integer.MAX_VALUE;
        int startPoint = 0;
        for(int i=1; i<=V; i++){
            if(distance[i] < min && !visited[i]){
                min = distance[i];
                startPoint = i;
            }
        }
        return startPoint;
    }
}

class Node {
        int end;
        int add;

    public Node(int end, int add) {
        this.end = end;
        this.add = add;
    }
}