최단 경로 - 다익스트라

 

 

 

가중치 그래프에서 가중치의 합이 최소가 되도록 하는 특정 경로를 찾는 알고리즘이다.

 

 

다익스트라 (Dijkstra)

 

 

그래프의 특정 노드에서 출발해 시작 노드를 제외한 나머지 모든 노드들에 대해 최단 경로를 찾는 알고리즘이다.

 

 

 

 

그림과 같은 그래프에서 A에서 출발해 B까지 가는 최단 경로를 구한다고 생각해보자. (가중치를 거리라고 생각하자)

A에서 B로 바로 가면 거리는 8이지만, C를 거쳐 B를 가면 6의 거리로 갈 수 있으니 여기서 최단 경로는 6이다.

 

 

 

A에서 출발해 B로 가는 최단 경로를 구해보자.

 

1. 시작 노드와 연결된 노드들에 대해 가중치를 저장할 배열을 만들고, 가중치를 저장한다.

A : [8(B), 1(C), 2(D)]

 

2. 저장된 가중치 중에서 최솟값이 가리키는 노드를 기준으로 설정하고 해당 노드와 연결된 모든 노드를 확인하고, 가중치 배열을 만들어 가중치를 저장한다.

C : [5(B), 2(D)]

 

3. A에서 C를 거쳐 B에 갈 경우 거리6으로 갈 수 있음을 확인했다. 배열을 업데이트한다.

A : [6(B), 1(C), 2(D)]

 

이런 방식으로 A에서 시작해 도착할 수 있는 모든 노드들에 대해서 최단거리를 갱신한다.

 

 

다익스트라는 전반적으로 위와 같은 방식으로 동작하고, 미루어 짐작할 수 있듯, BFS와 유사하다.

 

 

실제 코드로 구현할 때는 우선순위 큐를 사용해 최솟값을 가리키는 노드를 쉽게 찾을 수 있도록 하고, 우선순위 큐에는 노드 객체가 들어가야 하니 노드 객체를 만들고 정렬될 수 있도록 comparable인터페이스를 구현받고 compareTo메서드를 구현해야 한다.

 

 

 

코드로 구현해보자.

 

HashMap<String, ArrayList<Edge>> graph = new HashMap<String, ArrayList<Edge>>();
graph.put("A", new ArrayList<Edge>(Arrays.asList(new Edge(8, "B"), new Edge(1, "C"), new Edge(2, "D"))));
graph.put("B", new ArrayList<Edge>());
graph.put("C", new ArrayList<Edge>(Arrays.asList(new Edge(5, "B"), new Edge(2, "D"))));
graph.put("D", new ArrayList<Edge>(Arrays.asList(new Edge(3, "E"), new Edge(5, "F"))));
graph.put("E", new ArrayList<Edge>(Arrays.asList(new Edge(1, "F"))));
graph.put("F", new ArrayList<Edge>(Arrays.asList(new Edge(5, "A"))));

 

우선 해시맵에 그래프에 대한 정보를 넣어준다.

여기서 Edge객체는 가중치와 이어지는 노드를 의미한다.

 

 

import java.util.*;

public class Dijkstra {
    public HashMap<String, Integer> dijkstra(HashMap<String, ArrayList<Edge>> graph, String start) {
        Edge edgeNode, adjacentNode; 

        ArrayList<Edge> nodeList;
        int currentDistance, weight, distance;
        String currentNode, adjacent;

        HashMap<String, Integer> distances = new HashMap<String, Integer>(); // 가중치를 저장할 해시맵

        for (String key : graph.keySet()) { // for each loop
            distances.put(key, Integer.MAX_VALUE); // 처음에는 최대값으로 초기화 되어 있음
        }

        distances.put(start, 0); // 자신 노드는 가중치 0 으로 표현할 수 있음. 
        
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<Edge>();
        priorityQueue.add(new Edge(distances.get(start), start)); // 우선순위큐에도 처음에는 자신 노드를 넣어줌
                
        while (priorityQueue.size() > 0) {
            edgeNode = priorityQueue.poll(); // 우선순위큐에서 가중치가 가장 작은 값을 뺸다.
            currentDistance = edgeNode.distance;
            currentNode = edgeNode.vertex;
            
            if (distances.get(currentNode) < currentDistance) {
                continue;
            } // 가중치가 저장된 해시맵에 있는 가중치가 더 작으면 바꿔 줄 필요가 없다.
              // 안 되는 경우는 미리 처리해준다.
            
            nodeList = graph.get(currentNode); // 그래프에서 지금 탐색하는 노드와 연결된 노드들을 리스트에 저장함
            for (int index = 0; index < nodeList.size(); index++) {
                adjacentNode = nodeList.get(index); // 노드 정보 하나씩 가져오기

                adjacent = adjacentNode.vertex;
                weight = adjacentNode.distance;
                distance = currentDistance + weight; 
                
                if (distance < distances.get(adjacent)) { // 기록된 가중치보다 작은 가중치가 들어오면 가중치 갱신
                    distances.put(adjacent, distance); // 키 값으로는 중복을 허용하지 않아서 put으로 갱신한다.
                    priorityQueue.add(new Edge(distance, adjacent));
                }
            }
        }
        return distances;
    }
}

 

 

 

모든 간선을 검사하는 과정 : O(n)

우선순위 큐에 데이터를 추가하고 제거하는 과정 : O(n logn)

 

총 시간 복잡도 : O(n logn)