[Algorithm] Dijkstra's Algorithm (다익스트라 알고리즘)

1. Dijkstra's Algorithm

 

다익스트라 알고리즘은 한 정점으로부터 다른 정점으로의 최단 경로를 찾는 알고리즘이다.

매반복마다 현 시점에서 가장 가까운 정점을 찾아 해당 정점에 인접한 간선들을 통해 경로를 찾아 확장해 나가는 방식이다.

그래프의 방향 유무는 상관없으나 간선이 음수 가중치를 가지는 경우에는 사용할 수 없다.

 

 

2. 다익스트라 알고리즘 구현

 

1) 초기에 출발점으로부터 해당 정점으로의 거리를 저장할 공간과 방문여부를 저장할 공간을 선언한다.

2) 해당 배열에서 출발점은 0, 나머지 정점은 무한대로 초기화한다.

3) 최단 거리를 저장하는 배열에서 미방문 정점 중 가장 거리가 가까운 정점을 선택한다.

4) 해당 정점을 방문한 정점으로 저장한다.

5) 선택된 정점에 간선으로 연결된 인접한 정점들을 확인하여 현재 저장된 최단거리와 선택된 정점 + 간선의 크기를 비교하여 최단 경로 값을 업데이트한다.

6) 모든 정점을 방문할 때까지 3) ~5)를 반복한다.

 

다익스트라는 여러가지 방식으로 구현할 수 있는데, 여기서는 priority queue를 사용하여 현재 정점들의 최단거리를 찾는 방식으로 구현하였다.

 

    // src: 출발점의 인덱스
    private int[] dijkstra(int src) {
        int[] distance = new int[N]; // src로부터 다른 정점들까지의 최단 거리를 저장하는 배열
        for(int i = 0; i < N; i++) {
            if(i == src) continue;
            distance[i] = Integer.MAX_VALUE;
            pq.add(new Node(i, distance[i]));
        }
        distance[src] = 0;
        pq.add(new Node(src, 0));   // Node(정점의 인덱스, 정점의 최단거리)

        while(!pq.isEmpty()) {
            // priority queue에서 현재 최단 거리를 가지고 있는 정점을 구한다.
            Node node = pq.poll();
            if(visited[node.index])
                continue;
            
            // 미방문 정점인 경우 방문으로 바꾼 후 해당 정점과 인접한 정점들에 대해 거리를 계산, 비교한다.
            visited[node.index] = true;
            for(int i = 0; i < N; i++) {
                if(visited[i] || distance[i] < distance[node.index] + graph[node.index][i])
                    continue;
                distance[i] = distance[node.index] + graph[node.index][i];
                pq.add(new Node(i, distance[i]));
            }
        }

        return distance;
    }

- source code: https://github.com/rmk1075/CS/blob/main/Algorithm/Graph/Dijkstra/Dijkstra.java

 

 

3. 시간복잡도

 

시간복잡도는 구현의 방식에 따라 달라진다.

 

현재 최단 거리로 연결되어 있는 정점을 찾기 위해서 배열을 사용하여 matrix로 구현한 경우에는 매 반복마다 N개의 정점을 돌면서 아직 방문하지 않은 정점 중 최단경로를 가지고 있는 정점을 찾아야하기 때문에 O(N²)의 복잡도를 가진다.

 

반면에 힙구조를 사용하면 시간 복잡도를 O((E + V) logV)로 줄일 수 있다. 이는 heap에 각 정점마다 미방문 노드 중 최단 거리를 가지고 있는 노드를 찾는 데 O(V log V)의 시간이 걸리고, 각 정점마다 이웃한 정점의 최단 거리를 갱신할 때 O(E log V)의 시간이 걸리기 때문이다.

• O(V log V): 모든 정점 V에 대해서 힙에서 최소값을 추출 O(log V)
• O(E log V): 각 정점마다 모든 이웃을 확인하기 위해 모든 간선의 개수 E만큼 반복하면서, 매번 힙에서 최단거리를 갱신 O(log V)를 수행한다.

 

 

[reference]

- https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/

Dijsktra's algorithm

- https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98