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

다익스트라 알고리즘

그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.

 

다익스트라 알고리즘을 Java로 구현하기 위해서는 우선순위 큐(Priority Queue) 를 사용한다. 또한, 그래프의 노드 간선 관계를 나타내기 위해 Node 클래스를 구현해야 한다.

현재 탐색한 노드에서 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 이용함.

(우선 순위 기준 : 거리)

 

동작 원리

위 그래프에서 출발 노드를 1이라 하면, 우선 초기 상태에서는 모든 거리를 '무한'으로 초기화 한다. 이후 우선순위 큐에 출발 노드(1번)를 넣는다. (여기서 우선 순위 큐의 정렬 기준을 거리로 설정)

노드 번호	1	2	3	4	5	6
거리	0	무한	무한	무한	무한	무한

• 우선 순위 큐 | (거리:0, 노드:1)

 

1) 우선순위 큐에서 노드를 꺼낸다. 만약 해당 노드를 이미 처리한 적 있다면 무시한다.

- 꺼낸 원소 : (거리:0, 노드:1)

노드 번호	1	2	3	4	5	6
거리	0	2	5	1	무한	무한

• 우선 순위 큐 | (거리:1, 노드:4) (거리:2, 노드:2) (거리:5, 노드:3)

 

2) 위 과정을 반복한다.

- 꺼낸 원소 : (거리:1, 노드:4)

노드 번호	1	2	3	4	5	6
거리	0	2	4	1	2	무한

• 우선 순위 큐 | (거리:2, 노드:2) (거리:2, 노드:5) (거리:4, 노드:3) (거리:5, 노드:3) 

 

- 꺼낸 원소 : (거리:2, 노드:2)

노드 번호	1	2	3	4	5	6
거리	0	2	4	1	2	무한

• 우선 순위 큐 | (거리:2, 노드:5) (거리:4, 노드:3) (거리:5, 노드:3) 

 

- 꺼낸 원소 : (거리:2, 노드:5)

노드 번호	1	2	3	4	5	6
거리	0	2	3	1	2	4

• 우선 순위 큐 | (거리:3, 노드:3) (거리:4, 노드:3) (거리:4, 노드:6) (거리:5, 노드:3)

. . . (반복)

---

코드

입력 예시

6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2

static int n, m;                // 노드 수, 간선 수
static List<List<Node>> graph;  // 그래프
static int[] distance;          // 최단거리 배열

static class Node implements Comparable<Node> {
    int to;
    int cost;

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

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

public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    n = Integer.parseInt(st.nextToken());   // 노드 수
    m = Integer.parseInt(st.nextToken());   // 간선 수
    int start = Integer.parseInt(br.readLine());    // 시작 노드

    // 그래프 초기화
    graph = new ArrayList<>();
    for(int i=0; i<=n; i++) {
        graph.add(new ArrayList<>());
    }

    // 거리 배열 초기화
    distance = new int[n+1];
    Arrays.fill(distance, Integer.MAX_VALUE);

    // 간선 정보 입력
    for(int i=0; i<m; i++) {
        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        graph.get(a).add(new Node(b, c));
    }

    // 다익스트라 알고리즘 수행
    dijkstra(start);

    // 모든 노드로 가기 위한 최단 거리 출력
    for(int i=1; i<=n; i++) {
        // 도달할 수 없는 경우 무한이라고 출력
        if(distance[i] == Integer.MAX_VALUE)
            System.out.println("INFINITY");
        // 도달할 수 있는 경우 거리 출력
        else
            System.out.println(distance[i]);
    }
}

static void dijkstra(int start) {
    // PriorityQueue 생성
    PriorityQueue<Node> pq = new PriorityQueue<>();
    // 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
    pq.offer(new Node(start, 0));
    distance[start] = 0;

    while(!pq.isEmpty()) {
        // 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        Node cur = pq.poll();
        int dist = cur.cost;
        int now = cur.to;

        // 이미 처리된 노드는 무시
        if(distance[now] < dist) continue;
        // 현재 노드와 연결된 다른 인접한 노드들 확인
        for(Node node : graph.get(now)) {
            int newCost = dist + node.cost;
            if(newCost < distance[node.to]) {
                distance[node.to] = newCost;
                pq.offer(new Node(node.to, newCost));
            }
        }
    }
}