다익스트라(dijkstra)

*목차

1. 다익스트라 알고리즘이란?
2. 시간복잡도
3. 수도코드
4. 백준예제
5. 생각할 점

 

1. 다익스트라 알고리즘이란?

음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다.
방향그래프, 무방향 그래프 모두 상관 없으나, 가중치가 음수인 edge가 단 하나라도 존재하면 이 알고리즘은 사용할 수 없다.

 

2. 시간복잡도

(V는 정점, E는 정점의 이웃노드)

처음 고안한 알고리즘은 O(V^2)의 시간복잡도를 가졌다. 

이후 O((V+E)logV)의 우선순위 큐(=힙 트리)등을 이용한 더욱 개선된 알고리즘이 나왔다.

 

O((V+E)logV)의 시간복잡도를 가지는 이유는 각 노드마다 미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 O(VlogV)의 시간이 필요하고, 각 노드마다 이웃한 노드의 최단 거리를 갱신할 때 O(ElogV)의 시간이 필요하기 때문이다.

 

3. 수도코드

function dijkstra(G, S) //G는 Graph, S는 Source(출발점)
    for each vertex V in G //V는 특정 정점
        distance[V] <- infinite // 자기 이외의 모든 거리는 무한대
        previous[V] <- NULL  // 최적경로 초기화
        If V != S, add V to Priority Queue Q // V가 시작점이 아니면 우선순위 Queue에 추가
    distance[S] <- 0  // 본인의 거리는 당연히 0

    while Q IS NOT EMPTY //Q가 비어있지 않다면 루프안으로 이동
        U <- Extract MIN from Q  //Q에서 최소값 U 반환
            for each neighbour V of U // U의 이웃 확인
                tempDistance <- distance[U] + edge_weight(U, V) // S(출발점)~U까지의 거리 + U에서 V까지의 거리
                if tempDistance < distance[V]  // S(출발점)~V까지의 거리 비교
                    distance[V] <- tempDistance  //새로운 거리가 짧다면 거리 값 최신화
                    previous[V] <- U // 다음으로 살펴볼 정점은 가장 짧은 거리에 있는 정점
   return distance[], previous[]

 

distance[V] <- infinite

  출발지점 S와 모든 정점의 초기 거리는 모두 infinite를 사용한다.(자신과의 거리는 당연히 0이다.) 만약에 0으로 초기화한다면, 각 정점과 거리 비교 이전에 방문여부를 따져야 한다. 메모리 초과 오류가 날 수도 있다. 하지만 infinte를 사용하면 계속 최솟값만 비교하면 된다. (Integer.MAX_VALUE로 초기화)

 

Extract MIN from Q

  그냥 큐가 아닌 우선순위 큐이다. 어떤 순서로 값을 넣든지, 내부에서는 자동적으로 정렬을 한다. 그 기준은 내가 정할 수 있으며, 거리값에 따라서 최소값이 먼저 나올 수 있도록 한다.(PriorityQueue 사용, Comparable구현)경우에 따라 자동적으로 최솟값을 반환하는 경우 우선순위 큐가 필요 없다.

 

tempDistance <- distance[U] + edge_weight(U, V) 

  가장 핵심이 되는 거리 비교 알고리즘이다.

1. distance[U](시작~U까지의 최솟값)+edge_weight(U,V)(다음 정점까지의 이동거리)와

2. distance[V](시작~V까지의 최솟값)

2개를 비교해서 최솟값을 업데이트하고 다음 정점을 정한다.

 

 

4. 백준 1916 / 최소비용구하기

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

public class 다익스트라_1916_최소비용구하기 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());// 도시의 개수
		int M = Integer.parseInt(br.readLine());// 버스의 개수
		StringTokenizer st = null;
		List<int[]>[] list = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++)
			list[i] = new ArrayList<>();
		
		int[] dis = new int[N + 1];
		for (int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine());
			int city_start = Integer.parseInt(st.nextToken());
			int city_end = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());

			list[city_start].add(new int[] { city_end, cost });
		}
		st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		for(int i=1;i<=N;i++) {
			if(i==start)
				continue;
			dis[i]=Integer.MAX_VALUE;
		}
		
		PriorityQueue<DOT> queue = new PriorityQueue<>();
		queue.add(new DOT(start,0));
		
		while(!queue.isEmpty()) {
			DOT dot = queue.poll();
			int x = dot.x;
			int cost = dot.cost;
			
			for(int i=0;i<list[x].size();i++) {
				int city_end = list[x].get(i)[0];
				int newCost = list[x].get(i)[1]+cost;
				if(newCost<dis[city_end]) {
					dis[city_end]=newCost;
					queue.add(new DOT(city_end,newCost));
				}
			}
		}
		System.out.println(dis[end]);
	}
}

class DOT implements Comparable<DOT>{
	int x;
	int cost;
	public DOT(int x, int cost) {
		this.x=x;
		this.cost=cost;
	}
	
	@Override
	public int compareTo(DOT dot) {
		return this.cost-dot.cost;
	}
}

 

 

 

출처 : https://www.programiz.com/dsa/dijkstra-algorithm

https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

5. 생각 할 점

  입력으로 배열이 주어진다면 배열을 활용하는 경우가 많은데, 입력 값으로 정점과 거리가 주어진 경우에는 어디에 정보를 담을지 고민한다. 2차원 배열은 서로 관계가 없는 정점끼리는 0으로 표시하여 메모리를 차지하지만 List<ArrayList>[] list = new ArrayList[N+1] , List<int[]>[] list = new ArrayList[N+1] 등을 이용하면 서로 연결된 정점끼리만 정보를 추가하게 되어 적은 메모리를 차지한다. 주의할 점은 각각 list[i]의 배열을 초기화 해야한다!

 

라고 생각했는데, 과연 이 객체들이 더 가벼운지 무거운지는 상황에 따라 확인이 필요하다.(실제로 2차원 배열을 사용하다가 메모리 초과가 발생했다.) 간선만 너무 많은 경우, 정점만 너무 많은경우에는 다를 수 있지 않을까? Comparable을 구현만 하면 우선순위큐 이용이 가능하므로 2가지 모두 답을 구할 때 사용해보고 비교해보면 되겠다.