[문제풀이] 09-05. 다익스트라 알고리즘

인프런, 자바(Java) 알고리즘 문제풀이

Greedy Alogorithm - 0905. 다익스트라 알고리즘

---

🗒️ 문제

---

🎈 나의 풀이

	private static List<List<Edge>> graph = new ArrayList<>();
    private static int[] dis;
    private static int n, m;

    private static class Edge implements Comparable<Edge> {
        int vet;
        int cost;

        public Edge(int vet, int cost) {
            this.vet = vet;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            if (o.cost == this.cost) return o.vet - this.vet;
            return this.cost - o.cost;
        }
    }

    private static void solution() {
        for(int i=1; i<=n; i++) dis[i] = -1;
        dis[1] = 0;

        PriorityQueue<Edge> pQ = new PriorityQueue<>();
        pQ.add(new Edge(1, 0));

        while(!pQ.isEmpty()) {
            Edge now = pQ.poll();

            if(now.cost > dis[now.vet]) continue;

            for(Edge e : graph.get(now.vet)) {
                if(dis[e.vet] == -1 || dis[e.vet] > e.cost + now.cost) {
                    pQ.add(new Edge(e.vet, e.cost + now.cost));
                    dis[e.vet] = e.cost + now.cost;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        dis = new int[n+1];

        for(int i=0; i<n+1; i++) graph.add(new ArrayList<>());

        for(int i=0; i<m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();

            graph.get(a).add(new Edge(b, c));
        }

        solution();

        for(int i=2; i<=n; i++) {
            if(dis[i] == -1) System.out.println(i + " : impossible");
            else System.out.println(i + " : " + dis[i]);
        }
    }

---

🖍️ 강의 풀이

  class Edge implements Comparable<Edge>{
      public int vex;
      public int cost;
      Edge(int vex, int cost) {
          this.vex = vex;
          this.cost = cost;
      }
      @Override
      public int compareTo(Edge ob){
          return this.cost-ob.cost;
      }
  }

  class Main {
      static int n, m;
      static ArrayList<ArrayList<Edge>> graph;
      static int[] dis;
      public void solution(int v){
          PriorityQueue<Edge> pQ = new PriorityQueue<>();
          pQ.offer(new Edge(v, 0));
          dis[v]=0;
          while(!pQ.isEmpty()){
              Edge tmp=pQ.poll();
              int now=tmp.vex;
              int nowCost=tmp.cost;
              if(nowCost>dis[now]) continue;
              for(Edge ob : graph.get(now)){
                  if(dis[ob.vex]>nowCost+ob.cost){
                      dis[ob.vex]=nowCost+ob.cost;
                      pQ.offer(new Edge(ob.vex, nowCost+ob.cost));
                  }
              }
          }
      }

      public static void main(String[] args){
          Main T = new Main();
          Scanner kb = new Scanner(System.in);
          n=kb.nextInt();
          m=kb.nextInt();
          graph = new ArrayList<ArrayList<Edge>>();
          for(int i=0; i<=n; i++){
              graph.add(new ArrayList<Edge>());
          }
          dis=new int[n+1];
          Arrays.fill(dis, Integer.MAX_VALUE);
          for(int i=0; i<m; i++){
              int a=kb.nextInt();
              int b=kb.nextInt();
              int c=kb.nextInt();
              graph.get(a).add(new Edge(b, c));
          }
          T.solution(1);
          for(int i=2; i<=n; i++){
              if(dis[i]!=Integer.MAX_VALUE) System.out.println(i+" : "+dis[i]);
              else System.out.println(i+" : impossible");
          }
      }
  }

---

💬 짚어가기

다익스트라(Dijkstral) 알고리즘은 그래프 상에서 시작 정점부터 나머지 각 정점까지의
최단거리를 계산하는 알고리즘이다. 그래프의 어느 간선의 가중치라도 음수가 있으면 안된다.

🔎 다익스트라(Dijkstral) 알고리즘

1. 시작 정점 선택
   출발 정점을 선택하고, 이 정점에서 출발하는 최단 경로를 찾는다.

2. 가중치 초기화
   시작 정점에서 직접 연결된 정점들에 대한 가중치를 초기화한다.
   출발 정점에서 자기 자신으로의 거리는 0, 나머지는 무한대로 설정한다.

3. 최단 경로 갱신
   현재 선택한 정점과 연결된 정점들 중에서, 아직 방문하지 않은 정점을 선택한다.
   선택한 정점으로 가는 현재까지의 최단 경로가 기존보다 더 짧으면 해당 정점까지의
   최단 경로를 갱신한다. 방문한 정점 표시을 표시하고, 해당 정점의 최단 경로를 확정한다.

4. 더 이상 갈 곳이 없을 때까지 반복
   목적지에 도달하거나 더 이상 갈 곳이 없을 때까지 3단계를 반복한다.

이 과정을 통해 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾을 수 있다.
각 정점까지의 최단 경로는 해당 정점에 도달하는 데 필요한 최소 가중치(거리)를 나타낸다.

⏱️ 시간 복잡도 : $O(E$ $logV)$

간선의 수를 $E$(Edge), 노드의 수를 $V$(Vertex)라고 했을 때,

노드에 연결된 간선을 모두 확인(간선의 개수 만큼 반복) : $O(E)$
우선순위 큐(완전 이진 트리 구조)에서 간선을 넣고 빼는 과정 : $O(logE)$

$O(E$ $logE)$의 시간 복잡도를 갖는다.

이때, 중복 간선을 포함하지 않는 경우 간선의 개수는 항상 (노드의 개수)$^2$ 이하이다.
( 간선의 최대 개수 : 모든 노드가 연결 되어 있는 경우인 $V * (V-1)$ )

$logE$는 $log(V^2)$보다 작고, $log(V^2)$은 $2logV$와 같으므로, $O(logV)$로 표현할 수 있다.
따라서, 다익스트라 알고리즘의 시간 복잡도를 $O(E$ $logV)$로 표현할 수 있다.

✔️ 코드 구현 살펴보기

1. 초기화
   dis 배열을 초기화하고, 모든 정점까지의 거리를 무한대(-1로 표현)로 설정한다.
   시작 정점(1번 정점)의 거리를 0으로 설정한다.
   pQ(우선순위 큐)를 초기화하고 시작 정점을 큐에 추가한다.

2. 우선순위 큐에서 최단 거리 정점 선택 및 방문
   우선순위 큐에서 거리가 가장 짧은 정점을 선택하고 해당 정점을 방문한다.
   선택된 정점에서 현재까지의 최단 거리(dis)보다 큰 거리를 가지면 무시하고 넘어간다.

3. 선택한 정점에서 갈 수 있는 정점들의 거리 갱신
   선택한 정점과 연결된 정점들을 순회하면서 현재까지의 최단 거리와 비교한다.
   이미 방문한 정점인 경우
   현재까지의 거리와 해당 정점까지의 거리를 비교하여 더 짧은 거리로 갱신한다.
   아직 방문하지 않은 정점인 경우
   해당 정점으로 가는 거리를 계산하여 우선순위 큐에 추가하고 최단 거리를 갱신한다.

4. 반복
   우선순위 큐가 비어있을 때까지 2, 3 단계를 반복한다.
   각 단계를 통해 최단 거리가 갱신되고, 우선순위 큐에 새로운 후보들이 계속해서 추가된다.

5. 결과 출력
   최종적으로 각 정점까지의 최단 거리가 dis 배열에 저장되어 있다.
   결과를 출력하면서 각 정점에 도달할 수 있는 최단 거리를 표시한다.
   만약 도달할 수 없는 경우 impossible을 출력한다.