Dijkstra 알고리즘

최단 경로

최단 경로 문제(shortest path problem)는 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로를 찾는 문제로, 그래프 관련 문제 중에서 최단 경로 문제가 많다. 최단 경로 문제를 해결하기 위해서는 그래프가 어떤 그래프인지 파악하고, 그에 맞는 최단 경로 알고리즘을 적용해야한다.

 

최단 경로 알고리즘은 최단 경로를 구성하는 정점들의 목록을 구해 주는 것이 아닌 최단 경로의 길이를 찾아줄 뿐이라는 점에 유의해야한다. 실제 경로를 계산하기 위해서는 BFS에서 그랬듯이 탐색 과정에서 별도의 정보를 저장하고, 이것으로부터 실제 경로를 찾아내야한다.

 

가중치가 없는 그래프에서는 BFS로 최단 경로를 구할 수 있다. 여기서의 최단 경로는 경로의 길이가 가장 짧은 경로를 말한다.

 

가중치가 있는 그래프에서는 다익스트라, 벨만 포드, 플로이드 등의 다양한 알고리즘으로 구할 수 있다. 여기서의 최단 경로는 가중치 합이 가장 작은 경로를 말한다.

다익스트라 알고리즘

다익스트라는 BFS와 똑같다. BFS는 시작 정점에서 가까운 정점부터 방문한다. 이를 최단 경로로 방문한다고 한다. 다익스트라도 마찬가지다. 차이점은 최단 경로의 기준이다. 기준은 아래와 같다.

• BFS - 경로의 길이
• 다익스트라 - 경로의 가중치 합

다익스트라는 출발 정점에서 가장 가까운 정점들을 순차적으로 방문하는 단순한 알고리즘이다. 구현도 BFS와 유사한데 차이점은 아래와 같다.

• 큐 대신 우선순위 큐 (최단 경로를 빠르게 찾기 위해 사용)
• 같은 정점이 여러번 발견됨 (방문된 정점을 경유지로 하는 최단 경로가 있을 수 있기 때문)

다익스트라의 중요한 특징은 방문된 정점 (큐에서 나온 정점)의 최단 거리는 변하지 않는다. 이 같은 특징으로 다익스트라도 BFS와 같은 동작 방식을 가질 수 있는 것이다. 또한 간선이 음수이면 동작하지 않음을 보인다. 왜냐하면 간선이 음수일경우 방문되지 않은 정점을 경유지로 해 방문된 정점을 가는 최단 경로가 있을 수 있기 때문이다.

import java.io.*;
import java.util.*;

public class DilkstraVer1 {
	//그래프 인접 정보
	static class Node {
		int to;
		int weight;
		Node next;
		public Node(int to, int weight, Node next) {
			this.to = to;
			this.weight = weight;
			this.next = next;
		}
	}
	
	static class PQNode implements Comparable<PQNode> {
		int v;
		int totalDistance;
		public PQNode(int v, int totalDistance) {
			this.v = v;
			this.totalDistance = totalDistance; //v로 가는 경로의 최단 거리
		}
		@Override
		public int compareTo(PQNode o) {
			return Integer.compare(totalDistance, o.totalDistance);
		}
	}
	
	static int V;
	static Node[] adjList;
	static int[] distance;
	static final int INT = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		V = Integer.parseInt(st.nextToken()); 	  //정점 개수
		int E = Integer.parseInt(st.nextToken()); //간선 개수

		st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken()); //시작 정점
		int end =  Integer.parseInt(st.nextToken());  //도착 정점
		
		//인접 리스트 생성
		adjList = new Node[V];
		for(int i=0; i<E; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			adjList[from] = new Node(to, weight, adjList[from]);
		}

		//다익스트라 수행
		distance = new int[V]; //각 정점까지의 최단 거리 저장
		Arrays.fill(distance, INT);
		dijkStra(start);
		if(distance[end] == INT) System.out.println(-1);
		else System.out.println(distance[end]);
	}

	public static void dijkStra(int start) {
		distance[start] = 0;

		//방문해야할 정점의 목록 저장
		PriorityQueue<PQNode> pq = new PriorityQueue<>();
		pq.offer(new PQNode(0, distance[0]));

		while(!pq.isEmpty()) {
			PQNode pqNode = pq.poll();

			int v = pqNode.v;
			int totalDistance = pqNode.totalDistance;

			//v 정점이 이미 방문되었다면 무시 (방문된 정점의 최단 거리(distance) 값은 더 이상 줄일 수 없음)
			if(distance[v] < totalDistance) continue;
			
            //v 정점 방문
            
			/*
            v와 인접하고 아직 방문되지 않은 정점 A가 있을 때, v 정점을 경유지로 해 A로 가는 최단 경로가 있다면 distance[A]를 갱신하고 A를 큐에 넣음
            방문된 정점의 최단 거리는 더 이상 줄일 수 없으므로 발견되지 않음
            아직 방문되지 않은 정점은 여러번 발견될 수 있음 (최단 거리가 갱신되는 경우)
			*/
			for(Node node = adjList[v]; node != null; node = node.next) {
				int newDistance = distance[v] + node.weight;
				if(newDistance < distance[node.to]) {
					distance[node.to] = newDistance;
					pq.offer(new PQNode(node.to, newDistance)); //발견
				}
			}
		}
	}
}

위 코드의 수행 시간은 크게 두 부분으로 나누어 볼 수 있다. 하나는 각 정점마다 인접한 간선들을 모두 검사하는 작업이며, 다른 하나는 우선 순위 큐에 원소를 넣고 빼는 작업이다. 각 정점은 정확히 한 번씩 방문되고, 따라서 모든 간선은 한 번씩 검사되므로 인접 간선들을 검사하는 시간 복잡도는 O(E)이다.

 

우선 순위 큐에 원소를 넣고 삭제하는 작업의 시간 복잡도를 계산하려면 우선 순위 큐에 최대 크기가 얼마가 될 수 있는지 알아야 한다. BFS에서 각 정점은 한 번씩만 발견, 즉 큐에 한 번씩만 넣기 때문에 큐의 최대 크기는 V이지만 다익스트라에서 각 정점은 여러 번 발견될 수 있다. 최악의 경우 모든 간선이 검사될때마다 distance[]가 갱신되어 원소가 큐에 들어가는 경우로 이때 큐의 크기는 E가 된다. 우선 순위 큐에 원소를 넣고, 빼는 작업은 O(log E)의 시간이 걸리므로 전체 시간 복잡도는 O(E log E)가 된다.

 

두 작업의 시간 복잡도를 합치면 O(E) + O(E log E) = O(E log E)가 되며 위 코드의 시간 복잡도는 O(E log E) 임을 알 수 있다.

우선 순위 큐를 사용하지 않는 구현

아래는 우선순위 큐를 사용하지 않고 다익스트라 알고리즘을 구현하는 코드이다. 이 코드에서는 다음에 방문할 정점을 별도의 큐에 보관하는 대신 매번 반복문을 이용해 방문하지 않은 정점 중 distance[]가 가장 작은 값을 찾고 방문한다. 다음에 방문할 정점들의 목록이 없기 때문에, 방문 여부를 체크할 visit 배열이 필요하다. 아래 코드의 시간 복잡도는 O(E + V²)가 된다.

public class DilkstraVer2 {
	static class Node {
		int to;
		int weight;
		Node next;
		public Node(int to, int weight, Node next) {
			this.to = to;
			this.weight = weight;
			this.next = next;
		}
	}

	static int V;
	static Node[] adjList;
	static int[] distance;
	static final int INT = Integer.MAX_VALUE;

	public static void dijkStra(int start) {
		boolean[] visit = new boolean[V];
		Arrays.fill(distance, INT);
		distance[start] = 0;

		for(int i=0; i<V; i++) {
			int minV = -1;
			int minDistance = INT;
			for(int j=0; j<V; j++) {
				if(!visit[j] && distance[j] < minDistance) {
					minV = j;
					minDistance = distance[j];
				}
			}

			if(minDistance == -1) break;

			visit[minV] = true;
			for(Node node = adjList[minV]; node != null; node = node.next) {
				int newDistance = distance[minV] + node.weight;
				if(newDistance < distance[node.to]) {
					distance[node.to] = newDistance;
				}
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		V = Integer.parseInt(st.nextToken()); //정점 개수
		int E = Integer.parseInt(st.nextToken()); //간선 개수

		st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken()); //시작 정점
		int end =  Integer.parseInt(st.nextToken());  //도착 정점
		
		//인접 리스트 생성
		adjList = new Node[V];
		for(int i=0; i<E; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			adjList[from] = new Node(to, weight, adjList[from]);
		}

		//다익스트라 수행
		distance = new int[V];
		dijkStra(start);
		if(distance[end] == INT) System.out.println(-1);
		else System.out.println(distance[end]);
	}
}