[챗GPT로 코딩 공부] 다익스트라 알고리즘 코드로 구현하기

다익스트라 알고리즘의 기본 원리와 동작 방식

• 출발점 설정: 시작 노드를 선택하고 해당 노드까지의 거리를 0으로 초기화합니다.

• 초기화: 다른 모든 노드까지의 거리를 무한대로 설정합니다.

• 미방문 노드 중 최단 거리 선택: 아직 방문하지 않은 노드 중 시작점으로부터 가장 가까운 노드를 선택합니다.

• 거리 갱신: 선택한 노드를 거쳐 다른 노드로 가는 거리가 기존에 알고 있던 거리보다 짧으면 해당 거리 정보를 갱신합니다.

• 반복: 모든 노드를 방문할 때까지 3, 4 단계를 반복합니다.

다익스트라 알고리즘을 Java로 구현하는 방법

import java.util.*;

public class DijkstraAlgorithm {

    public static class Node implements Comparable<Node> {
        public int id;
        public int distance;

        public Node(int id, int distance) {
            this.id = id;
            this.distance = distance;
        }

        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.distance, other.distance);
        }
    }

    public static int[] dijkstra(int n, List<List<Node>> graph, int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        int[] distances = new int[n];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[start] = 0;

        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int currentId = current.id;

            for (Node neighbor : graph.get(currentId)) {
                int newDist = distances[currentId] + neighbor.distance;

                if (newDist < distances[neighbor.id]) {
                    distances[neighbor.id] = newDist;
                    pq.add(new Node(neighbor.id, newDist));
                }
            }
        }

        return distances;
    }

    public static void main(String[] args) {
        int n = 6;
        List<List<Node>> graph = new ArrayList<>();

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

        graph.get(0).add(new Node(1, 5));
        graph.get(0).add(new Node(2, 1));
        graph.get(1).add(new Node(2, 2));
        graph.get(1).add(new Node(3, 3));
        graph.get(2).add(new Node(3, 4));
        graph.get(3).add(new Node(4, 2));
        graph.get(4).add(new Node(5, 1));
        graph.get(5).add(new Node(3, 1));

        int[] distances = dijkstra(n, graph, 0);

        System.out.println("최단 경로: " + Arrays.toString(distances));
    }
}

다익스트라 알고리즘 구현 시 발생하는 오류 해결 방법

내일배움캠프가 여러분의 러닝메이트가 되어드리겠습니다

취업 준비, 어디서부터 시작해야 할지 모르겠다면?