Dijkstra (다익스트라)

1. 최단 경로 알고리즘

• 가중 그래프 상의 두 노드를 연결하는 가장 짧은 경로를 찾는 방법
• 지도 경로 탐색, 네트워크 구축에 드는 비용을 최소화 하는데 사용
• 최단 경로 알고리즘
  • 다익스트라
  • 벨만-포드
  • 플로이드-워셜

2. 다익스트라 (Dijkstra)

• 출발점에서 목표점까지의 최단경로를 구하는 알고리즘
• 한 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있음
• 간선에 음의 가중치가 없어야 함
• Greedy + DP 형태
• 알고리즘 복잡도 : O(ElogV)

3. 다익스트라 알고리즘 Flow

• 다음과 같이 노드와 간선 가중치 정보가 있을 때
  • A 노드에서 다른 노드들에 대한 최단 경로 구하기

(실습 : 다익스트라 코드)

// 다익스트라 우선순위 큐 사용

import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main2 {

    static class Node {
        int to;
        int weight;

        public Node(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
    public static void dijkstra(int v, int[][] data, int start) {
        ArrayList<ArrayList<Node>> graph = new ArrayList<>();
        for (int i = 0 ; i < v + 1 ; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0 ; i < data.length ; i++) {
            graph.get(data[i][0]).add(new Node(data[i][1], data[i][2]));
        }
        
        int[] dist = new int[v + 1];

        for (int i = 1 ; i < v + 1 ; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        dist[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> x.weight - y.weight);
        pq.offer(new Node(start, 0));

        while(!pq.isEmpty()) {
            Node curNode = pq.poll();

            if (dist[curNode.to] < curNode.weight) {
                continue;
            }

            for (int i = 0 ; i < graph.get(curNode.to).size(); i++) {
                Node adjNode = graph.get(curNode.to).get(i);

                if (dist[adjNode.to] > curNode.weight + adjNode.weight) {
                    dist[adjNode.to] = curNode.weight + adjNode.weight;
                    pq.offer(new Node(adjNode.to, dist[adjNode.to]));
                }
            }
        }

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

    }

    public static void main(String[] args) {
        // Test code 
        int[][] data = { {1, 2, 2}, {1, 3, 3}, {2, 3, 4}, {2, 4, 5}, {3, 4, 6}, {5, 1, 1} };
        dijkstra(5, data, 1);
    }
}