[알고리즘] 🤪이죵과 다익스트라(Dijkstra) 알고리즘을 알아보자

---

🎈 시작하기에 앞서 ..

오늘은 어떤걸올릴까 생각하다가 예전부터 그래프 알고리즘에 대한 개념을 정리해서 머리속에 박아 넣어놓고 싶었기 때문에 그래프 알고리즘을 하나씩 정리해 보고자 한다. 개인적으로 그래프 알고리즘은 문제에 맞는 알고리즘 기법을 아느냐 모르느냐에 따라 문제 접근시간과 풀이에 큰 차이가 있다고 생각한다.

그러므로 만약 그래프 알고리즘에 대한 정리가 되어있지 않다면! 이 글을 읽으며 함께 정리해 보는 시간이 되었으면 좋겠다 🥰

그렇다면 그래프 알고리즘에는 어떤것이 있을까?

어떤 알고리즘이 있는지 알아보기 전에 그래프 알고리즘은 어떤 유형으로 나오는지 알아보자면..

🎈 그래프 알고리즘의 유형

1. 두 정점 사이의 최단 경로찾기
   • 다익스트라 알고리즘(Dijkstra's Algorithm)
   • 벨만-포드 알고리즘(Bellman-Ford Algorithm)
   • 플로이드-와샬 알고리즘(Floyd-Warshall Algorithm)
2. 그래프의 모든 정점을 탐색하여 연결된 부분그래프를 찾기
   1. 깊이 우선 탐색(DFS, Depth-First Search)
   2. 너비 우선 탐색(BFS, Breadth-First Search)
3. 주어진 그래프의 모든 정점을 포함하는 트리(사이클X) 중에서 가중치의 합이 최소인 트리를 찾기
   1. 크루스칼 알고리즘(Kruskal's Algorithm)
   2. 프림 알고리즘(Prim's Algorithm)
4. 그래프에서 사이클이 존재하는지 찾기
5. 등…

이 이상은 본인이 겪으며 알아보도록 하자👼

그러므로 오늘은 다익스트라 알고리즘부터 함께 공부해보도록 하자! 👩‍🎤

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

• 하나의 정점(출발지)에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘
• 음수가중치를 갖을 수 없음.
• 시간복잡도
  • 우선순위 큐를 사용하는 개선된 다익스트라 알고리즘에는 O((V+E)log V)
    • 만약 연결그래프라면 O(ElogV)
  • 인접 행렬을 이용한경우의 시간복잡도는는 O(V^2)

🎈 다익스트라 알고리즘의 매커니즘

• 다익스트라 = 그리디 + DP기법을 사용한 알고리즘
• 알고리즘 흐름
  1. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다. (그리디)
  2. 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다. (DP)
• 해당 흐름을 반복한다.

🎈 예시

이러한 가중치를 갖는 그래프가 있다고 생각해보자

우선 시작점을 A로 잡고 방문하지않은 노드와, 방문한 노드 그리고 A에서 다른 B~F까지의 최소비용값을 체크해준다. 이때 최소비용의 초기값은 MAX로 설정해준다.

여기서 A 자기자신으로 가는 최소비용은 0원이다. 또한 A는 B,C,D로 이동할 수 있다.

A가 이동할 수 있는만큼 전부 이동했다면 방문하지 않는 노드 중 가장 적은 비용의 노드는 B이므로 B를 방문하고 B에서 이동할 수 있는 값을 전부 체크해준다.

이때 C로 이동하는 비용이 7이므로 기존의 비용보다 더 비싸므로 이전 값을 유지한다.

또한 F로 이동이 가능하므로 비용을 갱신해준다.

B의 방문이 끝났다면 남아있는 노드 중 적은 비용의 노드는 D이다.

D에서는 C와 E로 이동이 가능하고 C와 E로 이동했을때의 비용이 현재의 비용보다 더 저렴하므로 변경해준다.

그 후 남아있는 C,E,F중 가장 적은 비용의 노드는 C이므로 C로 이동해준다.

C에서 현재 방문하지 않은 노드는 E,F이고 두곳 모두 C를 통해서 이동하는 것이 비용이 더 저렴하므로 변경해준다.

남아있는 E,F중에서는 E가 더 저렴하므로 E로 이동한다.

E에서 이동할 수 있는 남은 노드는 F이고 비용이 더 저렴하므로 변경해준다.

최종적으로 F까지 모든 노드를 체크했을때는 각 노드로 이동할 수 있는 최소의 값이 이렇게 남게된다.

🎈 다익스트라(Dijkstra) 알고리즘 Java 코드

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

public class Dijkstra {
    static class Node{
        int v; //간선
        int cost; //가중치

        public Node(int v, int cost) {
            this.v = v;
            this.cost = cost;
        }
    }

    //각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
    static ArrayList<Node>[] graph;
    //방문한 적이 있는지 체크하는 목적의 리스트
    static boolean[] visit;
    //최단 거리 테이블
    static int[] dist;

    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());
        int k = Integer.parseInt(br.readLine());

        graph = new ArrayList[v + 1];
        dist = new int[v + 1];
        visit = new boolean[v + 1];

        for (int i = 1; i <= v; i++) {
            graph[i] = new ArrayList<>();
            dist[i] = Integer.MAX_VALUE; // 최대값으로 초기화
        }

        for (int i = 0; i < e; i++) {
            // a -> b의 비용 cost
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            graph[a].add(new Node(b, cost));
        }

        //다익스트라 알고리즘
        dijkstra(k);

        for (int i = 1; i <= v; i++) {
            System.out.println(dist[i] == Integer.MAX_VALUE ? "INF" : dist[i]);
        }
    }

    static void dijkstra(int start) {
        //우선 순위 큐 사용, 가중치를 기준으로 오름차순 정렬함.
        PriorityQueue<Node> q = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        //시작 노드에 대해서 초기화
        q.add(new Node(start, 0));
        dist[start] = 0;

        while (!q.isEmpty()) {
            // 최단 거리가 가장 짧은 노드를 꺼내서 방문 처리
            Node now = q.poll();

            if (!visit[now.v]) {
                visit[now.v] = true;
            }

            for (Node next : graph[now.v]) {

                //방문하지 않았고, 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧을 경우 바꿔주기
                if (!visit[next.v] && dist[next.v] > now.cost + next.cost) {
                    dist[next.v] = now.cost + next.cost;
                    q.add(new Node(next.v, dist[next.v]));
                }
            }
        }
    }
}

이제 코드를 익혔다면 백준에서 다익스트라 태그가 붙은 문제를 풀어보자 😊