다익스트라 알고리즘

다익스트라 알고리즘은 최소 비용 신장 트리(MST)와는 달리 

방향 그래프만 아니라, [무방향] 그래프에서도 적용이 가능하다. 

 

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

public class  Main {

    private static final int INF = 10000;

    //다익스트라 최단 경로
    // 1. 하나의 시작 정점을 두고, 다른 모든 정점을 목적지로 하여 최단 경로를 구하는 것이다
    // -> 모든 정점을 시작점으로 두고, 다른 모든 정점까지의 최단 경로는 [플로이드-워샬] 알고리즘으로 구한다.
    // 2. 가중치가 있는 가중치 그래프를 전제로 한다.(가중치가 없으면, BFS로 최단 경로 구하면 됨)
    // -> 시작 노드에서 목적지 노드까지의 가중치의 합이 최소인 경로가 최단 경로이다.
    // 3. 인접 행렬을 이용한다.

    // 인접 행렬
    private static int weight[][] = {  {0,10,5,INF,INF},
                                    {INF,0,2,1,INF},
                                     {INF,3,0,9,2},
                                {INF,INF,INF,0,4},
                                     {7,INF,INF,6,0}};

    private static int distance[] = new int[5];

    private static HashSet<Integer> hashset = new HashSet<>();
    public static void main(String[] args) {

        // 1. 인접 행렬을 만든다.
        // -> 인접 노드가 아니면, 0이 아닌 무한대(EX.Integer.MAX_VALUE..)를 삽입
        // -> 인접 행렬의 대각선은 무조건 0이여야 한다.(노드 자기 자신이 시작 노드이자 목적지 노드라고 생각하면 왜 0이여야 하는지 납득이 갈 것이다)

        // 2. 집합 (S)를 만든다(집합 S의 노드들은 이미 최단 경로가 확정된 노드들의 집합이라고 생각하면 편안~!)
        // -> 최단 경로의 길이가 확정된 노드를 표시하기 위함!(집합 S에 모든 노드들이 다 저장이 되면 다익스트라 알고리즘이 종료)

        // 3. distance 배열을 만든다
        // -> 만약 {A,B,C}라는 노드 3개가 있는 가중치 그래프이고, 시작 노드를 A라고 했을 때,
        // -> distance[0] = 인접행렬[A][A], distance[1] = 인접행렬[A][B], distance[2] = 인접행렬[A][C]로 초기화를 하며
        // -> 이 distance의 값들을 집합(S)에 포함되지 않은 노드 중, 경로의 길이가 가장 짧은 노드를 집합(S)에 포함시켜서,
        // -> 그 노드 이외에 다른 목적지 노들들이 만약 해당 노드를 경유하여 가는 경우가 더 경로가 짧아 진다면
        // -> ditance의 값을 갱신을 하고, 경로가 같거나 더 길어지면 갱신을 하지 않는다.


        // 0노드를 시작 노드라고 하자(나머지 노드들은 전부 목적지 노드가 된다)

        for(int x = 0;x < 5; x++)
            distance[x] = weight[0][x];

        hashset.add(0);
        distra(0);

        System.out.println("123");

    }

    static void distra(int startNode){

        for(int count = 0; count < 5-1;count++) {

            int nextNode = nextShortestNode();

            hashset.add(nextNode);

            // nextNode를 경유하는 경우(distance[nextNode] + weight[nextNode][목적지 노드])와 경유하지 않는 경우(distance[목적지 노드])를 비교!
            for (int x = 0; x < 5; x++) {

                if (hashset.contains(x) == false) {

                    int case1 = distance[nextNode] + weight[nextNode][x];
                    int case2 = distance[x];

                    if (case1 < case2)
                        distance[x] = case1;

                }
            }
        }

    }

    static int nextShortestNode(){

        int min = Integer.MAX_VALUE;
        int min_node = -1;
        for(int x = 0; x < 5; x++){

            if(hashset.contains(x) == false){

                if(min >= distance[x]) { // min_node가 -1이 반환되지 않게 "="을 붙여줘야함

                    min = distance[x];
                    min_node = x;
                }
            }
        }

        return min_node;

    }
}

 

 

아래와 같이 [인접 리스트]와 [우선 순위 큐]를 이용하여 구할 수도 있다.(백준 다익스트라 문제 참고)

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

public class  Main {

    private static final int INF = 3000001;

    private static int v,e,start_node;


    //인접 리스트를 이용한 다익스트라!
    private static LinkedList<int[]> list[];

    private static PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[1] - o2[1];
        }
    });

    private static int distance[];

    private static int set[];

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    private static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {


     StringTokenizer st = new StringTokenizer(br.readLine()," ");
     v = Integer.parseInt(st.nextToken());
     e = Integer.parseInt(st.nextToken());

     st = new StringTokenizer(br.readLine(),"");
     start_node = Integer.parseInt(st.nextToken());



     list = new LinkedList[v+1];
        for(int x = 0; x <= v;x++)
            list[x] = new LinkedList<>();

     distance = new int[v+1];
     set = new int[v+1];

     for(int x = 0; x < e; x++){

         st = new StringTokenizer(br.readLine());
         int row = Integer.parseInt(st.nextToken());
         int column = Integer.parseInt(st.nextToken());
         int w = Integer.parseInt(st.nextToken());

         //방향 그래프
        list[row].add(new int[]{column,w});

     }


       dikstra(start_node);

        for(int x = 1; x <= v;x++) {

            if(distance[x] != INF)
                sb.append(distance[x]).append("\n");
            else
                sb.append("INF").append("\n");

        }

        System.out.println(sb);

    }

    static void dikstra(int start_node){

        for(int x = 1; x <= v;x++)
            distance[x] = INF;
        distance[start_node] = 0;

        
        pq.add(new int[]{start_node,0});

        while (pq.isEmpty() != true) {

            int[] next = pq.poll(); // 여기서 [poll() 되는 노드]는 최단 경로가 확정이 된 노드이다.
            int node = next[0];
            int weight = next[1];

            for(int temp[]:list[node])
            {
                int nnode = temp[0];
                int ncost = temp[1];

                if(distance[nnode] > weight + ncost)
                {
                    distance[nnode] = weight + ncost;
                    pq.add(new int[]{nnode,distance[nnode]}); // 갱신이 된 노드를 저장!

                }
            }

        }
    }
}