[개념 정리] 최단 거리 알고리즘 - 다익스트라

가중치가 없는 그래프의 최단거리 문제는 대부분 BFS로 해결할 수 있습니다. 하지만, 간선에 가중치가 존재한다면 BFS가 아닌 최단거리 알고리즘을 통해 접근해야 합니다. 일반적으로 가중치 그래프의 최단거리 문제는 다음과 같은 유형이 존재합니다.

1. 두 정점 간의 최단 거리를 구하는 문제
2. 하나의 정점에서 다른 모든 정점과의 최단거리를 구하는 문제
3. 하나의 정점으로 가는 모든 최단 경로를 구하는 문제
4. 정점 간의 모든 최단 경로를 구하는 문제 - 플로이드-와샬

저번 글에서는 4번 유형을 해결하기 위한 플로이드-와샬 알고리즘에 대해 알아보았습니다. 이번 글에서는 2번 유형을 해결할 수 있는 다익스트라 알고리즘에 대해서 알아보겠습니다.

---

다익스트라 알고리즘은 간단하게 설명하면 시작 정점에서 거리가 최소인 정점을 선택해 나가며 최단거리는 구하는 방식입니다. 해당 과정을 간단한 수도코드로 나타내면 같습니다.

V -> 정점의 개수
Start -> 시작 정점
Adjacency -> 인접행렬 or 인접 리스트
Distance -> 시작 정점부터 각 정점간의 최단거리
Visited -> 최단거리가 갱신되었는지 체크

for i in (1 to V) :
	Distance[i] = Adjacency[Start][i]

for 모든 정점의 최단거리를 갱신했을 경우 :	
	update_vertex = Distance 중 최소값을 가지는 정점
	visited[i] = true;

	for adj_vertex in update_vertex의 인접 정점 :
		Distance[adj_vertex] = Min(Distance[adj_vertext], 
        			Distance[update_vertex] + Adjacency[update_vertex][adj_vertex][])

Distance 배열은 시작 정점(Start)로부터 각 정점까지의 최단거리를 유지하는 배열입니다. 먼저 인접행렬의 정보를 통해 해당 배열을 초기화해줍니다. 이후 모든 정점에 대해 최단 거리를 갱신하는 작업을 진행합니다. 이 과정은 다음과 같은 과정을 거치게 됩니다.

• 현재 방문한 정점들(visited = true)과 가장 가까운 거리에 있는 정점을 선택합니다. => update_vertex
• 해당 정점을 방문 체크합니다.
• 해당 정점(update_vertex)의 인접 정점(adj_vertex)을 순회하면서 update_vertex를 거쳐서 adj_vertex로 가는 거리가 더 가깝다면 Distance[adj_vertex]를 해당 값으로 갱신합니다.

위의 과정을 모든 정점이 방문될 때까지 반복하면 시작 정점부터 모든 정점과의 최단거리를 저장하고 있는 Distance 배열을 구할 수 있습니다.

---

 

백준에서 다익스트라 기본문제인 1753. 최단경로 문제는 다음과 같습니다.

 

위의 수도코드를 이용해 Java로 구현한 정답은 다음과 같습니다.

public class Solution1753 {
    static final int INF = 10 * 20001;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static HashMap<Integer, Integer>[] adj;
    static boolean[] visited;
    static int[] distance;
    static int V, E, start;
    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        V = Integer.parseInt(input[0]);
        E = Integer.parseInt(input[1]);
        adj = new HashMap[V + 1];
        visited = new boolean[V + 1];
        distance = new int[V + 1];

        start = Integer.parseInt(br.readLine());

        for (int i = 1; i < V + 1; i++) {
            adj[i] = new HashMap<>();
        }

        for (int i = 0; i < E; i++) {
            String[] line = br.readLine().split(" ");
            int src = Integer.parseInt(line[0]);
            int dest = Integer.parseInt(line[1]);
            int weight = Integer.parseInt(line[2]);
            if (adj[src].containsKey(dest) && adj[src].get(dest) > weight) {
                adj[src].put(dest, weight);
            } else if (!adj[src].containsKey(dest)) {
                adj[src].put(dest, weight);
            }
        }

        // init distance
        for (int i = 1; i < V + 1; i++) {
            if (start == i) {
                distance[i] = 0;
                continue;
            }

            if (!adj[start].containsKey(i))
                distance[i] = INF;
            else
                distance[i] = adj[start].get(i);
        }

        djkstra();

        for (int i = 1; i < V + 1; i++) {
            if (distance[i] == INF)
                System.out.println("INF");
            else
                System.out.println(distance[i]);
        }
    }

  private static void djkstra() {
      for (int id = 1; id < V + 1; id++) {
          int idx = -1;
          int minDist = INF;
          for (int i = 1; i < V + 1; i++) {
              if (visited[i] || minDist < distance[i]) continue;
              idx = i;
              minDist = distance[i];
          }

          visited[idx] = true;
          if (minDist == INF) continue;
          for(Integer dest : adj[idx].keySet()) {
              int weight = adj[idx].get(dest);
              if (visited[dest] || distance[dest] <= distance[idx] + weight) continue;
              distance[dest] = distance[idx] + weight;
          }
      }
  }
}

해당 문제는 정점의 개수가 200,000개이기 때문에 인접 리스트로 표현하였습니다. 여기서 한 가지 문제 존재하는데 위의 코드는 O(V^2)의 시간복잡도를 가지게 정점이 많은 경우에는 시간 초과가 발생할 수 있습니다.

---

여기서 최적화 시킬 수 있는 부분은 현재 방문한 영역과 최단거리를 갖는 정점을 구하는 부분입니다. 단순히 배열로 저장하는 것이 아닌 우선 순위 큐를 통해 해당 과정을 수행한다면 O(N) => O(logN)으로 단축할 수 있고 최종적으로 O((|E| + |V|) * logV)의 시간복잡도로 최적화가 가능합니다.

우선 순위큐를 통해 구현한 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class Solution1753 {
    static class Edge implements Comparable<Edge> {
        int id;
        int weight;
        public Edge(int id, int weight) {
            this.id = id;
            this.weight = weight;
        }


        @Override
        public int compareTo(Edge o) {
            return Integer.compare(this.weight, o.weight);
        }
    }
    static final int INF = 10 * 20001;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static ArrayList<Edge>[] adj;
    static boolean[] visited;
    static int[] distance;
    static int V, E, start;
    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");
        V = Integer.parseInt(input[0]);
        E = Integer.parseInt(input[1]);
        adj = new ArrayList[V + 1];
        visited = new boolean[V + 1];
        distance = new int[V + 1];

        start = Integer.parseInt(br.readLine());

        for (int i = 1; i < V + 1; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < E; i++) {
            String[] line = br.readLine().split(" ");
            int src = Integer.parseInt(line[0]);
            int dest = Integer.parseInt(line[1]);
            int weight = Integer.parseInt(line[2]);
            adj[src].add(new Edge(dest, weight));
        }

        // init distance
        for (int i = 1; i < V + 1; i++) {
            if (start == i) {
                distance[i] = 0;
                continue;
            }
            distance[i] = INF;
        }

        djkstra();

        for (int i = 1; i < V + 1; i++) {
            if (distance[i] == INF)
                System.out.println("INF");
            else
                System.out.println(distance[i]);
        }
    }

    private static void djkstra() {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(start, 0));
        while(!pq.isEmpty()) {
            Edge cur = pq.poll();

            if (cur.weight > distance[cur.id]) continue;
            for (int i = 0; i < adj[cur.id].size(); i++) {
                Edge next = adj[cur.id].get(i);
                if (distance[next.id] > distance[cur.id] + next.weight) {
                    distance[next.id] = distance[cur.id] + next.weight;
                    pq.add(new Edge(next.id, distance[next.id]));
                }
            }
        }
    }
}

여기서 주목할 부분은 기존의 visited를 통해 방문체크를 해줬던 것과 달리 우선 순위큐를 사용하게 되면 거리를 갱신한 후, 현재 거리가 distance의 값보다 클 경우 건너 뜀으로써 방문 체크를 할 수 있다는 점입니다. 

---

이번 글에서는 한 정점에서 다른 모든 정점까지의 최단 거리를 구할 수 있는 다익스트라 알고리즘에 대해서 알아보았습니다. 추가로 코드를 작성하며 쉽게 헷갈릴 수 있는 부분들에 대해 잘 정리된 글이 있어서 해당 글을 읽어보시는 것도 추천드립니다.

참고 자료

www.secmem.org/blog/2019/01/09/wrong-dijkstra/