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

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

다익스트라(Dijkstra) 알고리즘은 한 정점에서 다른 모든 정점으로 가는 최단경로를 구하는 알고리즘입니다.

다익스트라 알고리즘은 첫 정점을 기준으로 연결되어 있는 정점을 추가해가면서 최단거리를 갱신하는 DP(Dynamic Programming)문제입니다.

정점을 잇기 전까지는 시작점을 제외한 모든 정점은 무한대입니다.

다익스트라 알고리즘 동작

1. 출발 정점을 선택합니다.
2. 출발 정점에 연결되어있는 각 정점의 최단거리를 갱신합니다.
3. 방문하지 않은 정점 중 가장 거리가 짧은 정점을 선택합니다.
4. 선택한 정점에 연결되어 있는 각 정점의 최단거리를 갱신합니다.
5. 3~4번을 반복합니다.

예시

n = 노드갯수
k = 시작노드
[소스노드, 타겟노드, 거리]

[
    [1,2,6],
    [1,3,2],
    [1,4,3],
    [2,3,3],
    [2,4,5],
    [2,5,4],
    [3,4,2],
    [4,2,1]
]
n = 5,
k = 1

 

위와 같은 그래프가 있고 시작점이 1일때 초기상태입니다.

시작점인 1을 제외한 나머지 정점들의 거리는 아직 갱신되지 않았기 때문에 무한대입니다.

1	2	3	4	5
0	INF	INF	INF	INF

 

여기서 출발 정점에 연결되어있는 각 정점의 최단거리를 갱신합니다.

• 2번 정점: min(1번 최단거리(INF), 1번 최단거리(0) + 1->2거리(6))
• 3번 정점: min(3번 최단거리(INF), 1번 최단거리(0) + 1->3거리(2))
• 4번 정점: min(4번 최단거리(INF), 1번 최단거리(0) + 1->4거리(3))

1 (방문)	2	3	4	5
0	INF	INF	INF	INF
0	6	2	3	INF

방문하지 않은 정점 중 가장 거리가 짦은 정점을 선택하고 방문합니다.

방문한 정점에 연결되어있는 각 정점의 최단거리를 갱신합니다.

• 4번 정점: min(4번 최단거리(3), 3번 최단거리(2) + 3->4거리(2))

1 (방문)	2	3 (방문)	4	5
0	INF	INF	INF	INF
0	6	2	3	INF

 

 

방문하지 않은 정점 중 가장 거리가 짦은 정점을 선택하고 방문합니다.
방문한 정점에 연결되어있는 각 정점의 최단거리를 갱신합니다.

• 2번 정점: min(2번 최단거리(6), 4번 최단거리(3) + 4->2거리(1))

1 (방문)	2	3 (방문)	4 (방문)	5
0	INF	INF	INF	INF
0	6	2	3	INF
0	4	2	3	INF

 

 

방문하지 않은 정점 중 가장 거리가 짦은 정점을 선택하고 방문합니다.
방문한 정점에 연결되어있는 각 정점의 최단거리를 갱신합니다.

• 5번 정점: min(5번 최단거리(INF), 2번 최단거리(4) + 2->5거리(4))

1 (방문)	2 (방문)	3 (방문)	4 (방문)	5
0	INF	INF	INF	INF
0	6	2	3	INF
0	4	2	3	INF
0	4	2	3	8

 

 

방문하지 않은 정점 중 가장 거리가 짦은 정점을 선택하고 방문합니다.
방문한 정점에 연결되어있는 각 정점의 최단거리를 갱신합니다.

• 연결된 정점 없음. (PASS)

1 (방문)	2 (방문)	3 (방문)	4 (방문)	5 (방문)
0	INF	INF	INF	INF
0	6	2	3	INF
0	4	2	3	INF
0	4	2	3	8

 

이제 더 방문할 노드가 없으므로 최단거리 갱신을 끝냅니다.
이 알고리즘은 단순 선형탐색 알고리즘으로 O(n^2)의 시간복잡도를 가집니다.

우선순위 큐를 이용하면 선형탐색 시간을 줄여 시간복잡도를 O(nlogn)으로 만들 수 있습니다.

선형탐색 코드 (java)

leetcode 743번 문제 (https://leetcode.com/problems/network-delay-time/)

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<int[]>> graph = new HashMap();
        for (int[] info : times) {
            // info[0]: sourceNode, info[1]: targetNode, info[2]: time
            if (!graph.containsKey(info[0])) {
                graph.put(info[0], new ArrayList<int[]>());
            }
            graph.get(info[0]).add(new int[]{info[1], info[2]});
        }

        Map<Integer, Integer> dist = new HashMap();
        for (int i = 1; i <= n; i++) {
            dist.put(i, Integer.MAX_VALUE);
        }
        dist.put(k, 0);

        boolean[] visited = new boolean[n+1];

        while (true) {
            int node = -1;
            int nodeDist = Integer.MAX_VALUE;
            for (int i = 1; i <= n; i++) {
                if (!visited[i] && dist.get(i) < nodeDist) {
                    nodeDist = dist.get(i);
                    node = i;
                }
            }

            if (node < 0) break;

            visited[node] = true;
            if (graph.containsKey(node)) {
                for (int[] info : graph.get(node)) {
                    dist.put(info[0], Math.min(dist.get(info[0]), dist.get(node) + info[1]));
                }
            }
        }

        int ans = 0;
        for (int d : dist.values()) {
            if (d == Integer.MAX_VALUE) {
                return -1;
            }
            ans = Math.max(ans, d);
        }

        return ans;
    }
}

우선순위큐 코드 (java)

leetcode 743번 문제 (https://leetcode.com/problems/network-delay-time/)

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<int[]>> graph = new HashMap();
        for (int[] edge : times) {
            if (!graph.containsKey(edge[0])) {
                graph.put(edge[0], new ArrayList<int[]>());
            }
            graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
        }

        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((info1, info2) -> info1[0] - info2[0]);
        pq.offer(new int[]{0, k});

        Map<Integer, Integer> dist = new HashMap();

        while (!pq.isEmpty()) {
            int[] info = pq.poll();
            int d = info[0];
            int node = info[1];
            if (!dist.containsKey(node)) {
                dist.put(node, d);
                if (graph.containsKey(node)) {
                    for (int[] edge : graph.get(node)) {
                        int nnode = edge[0];
                        int nd = edge[1];
                        if (!dist.containsKey(nnode)) {
                            pq.offer(new int[]{d+nd, nnode});
                        }
                    }
                }
            }
        }

        if (dist.size() != n) {
            return -1;
        }

        int ans = 0;
        for (int cand : dist.values()) {
            ans = Math.max(ans, cand);
        }
        return ans;
    }
}