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

다익스트라 (Dijkstra)

• 모든 간선의 가중치가 '음이 아닌 경우' 의 유향 그래프 최단 경로 알고리즘
• '한 정점' → '모든 정점' 까지의 최단 경로 구하기
• 우선순위 큐 사용O 시간복잡도 : O(E log V)
• 우선순위 큐 사용X 시간복잡도 : O(V ^ 2 + E)
• 정점 수 대비 간선의 수가 많은 경우 (간선 밀도가 높은 경우)에는 우선순위 큐를 사용하지 않는 경우가 더 빠르다.
• 모든 간선의 가중치가 같다면 BFS로 최단 경로를 구할 수 있지만 그렇지 않은 경우엔 다익스트라 사용
• BFS 기반
• 그리디 알고리즘 (Greedy Algorithm)

 

알고리즘

1. 시작점 start로부터의 정점들까지의 최단거리를 나타내는 dist 배열을 둔다.
2. dist[start] = 0, 나머지는 무한대로 설정한다.
3. queue에 start를 넣는다.
   1. 현재 노드에 연결된 노드들의 최단 거리를 갱신한다.
   2. 아직 방문하지 않은 노드들 중 최단 거리를 가진 노드를 queue에 넣는다.
   3. 더 이상 방문 할 수 있는 노드들이 없으면 종료한다.

 

고려 사항

• 노드 간의 여러 개의 edge가 있을 수 있음
• 도달할 수 없는 정점도 존재한다.

---

예시 (백준 1916번)

1916번: 최소비용 구하기

1) 우선순위 큐 사용 O

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

import java.util.*
import java.util.function.BiFunction
import kotlin.collections.ArrayList
import kotlin.collections.HashMap
import kotlin.math.max
import kotlin.math.min
import kotlin.text.StringBuilder

var br = BufferedReader(InputStreamReader(System.`in`))
var bw = BufferedWriter(OutputStreamWriter(System.out))

val INF = 3000001

var V = 0
var E = 0
var K = 0
var graph = ArrayList<ArrayList<Edge>>()
lateinit var dist : Array<Int>

fun solution() {

    var strtok = StringTokenizer(br.readLine())
    V = strtok.nextToken().toInt()
    E = strtok.nextToken().toInt()

    K = br.readLine().toInt()

    for(i in 0.. V)
        graph.add(ArrayList())

    for(i in 0 until E)
    {
        strtok = StringTokenizer(br.readLine())
        var from = strtok.nextToken().toInt()
        var to = strtok.nextToken().toInt()
        var weight = strtok.nextToken().toInt()

        graph.get(from).add(Edge(from, to, weight))
    }

    dist = Array(V + 1, {INF})
    dist[K] = 0

    dijkstra()

    dist.filterIndexed { index, i -> index > 0 }.forEach {
        if(it == INF)
            bw.write("INF")
        else
            bw.write(it.toString())
        bw.newLine()
    }
}

fun dijkstra()
{
    var visited = BooleanArray(V + 1)

    var queue = PriorityQueue<Node>(kotlin.Comparator { o1, o2 -> o1.distance - o2.distance })
    queue.offer(Node(K, dist[K]))

    while(!queue.isEmpty())
    {
        var now = queue.poll()

        if(visited[now.num])
            continue
        visited[now.num] = true

        for(i in 0 until graph[now.num].size)
        {
            var next = graph[now.num][i]

            if(dist[next.to] > dist[now.num] + next.weight)
            {
                dist[next.to] = dist[now.num] + next.weight

                if(!visited[next.to])
                    queue.offer(Node(next.to, dist[next.to]))
            }
        }
    }
}

data class Edge(var from : Int, var to : Int, var weight : Int)
data class Node(var num : Int, var distance : Int)


fun main() {
    solution()


    br.close()
    bw.close()
}

 

2) 우선순위 큐 사용 X

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;


public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	static int V, E;
	static int start, finish;
	static int dist[];
	static ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
	static boolean visited[];

	public static void solution() throws Exception
	{
		V = Integer.parseInt(br.readLine());
		E = Integer.parseInt(br.readLine());

		visited = new boolean[V+1];

		for(int i = 0;i <= V;i++)
			graph.add(new ArrayList<>());

		for(int i = 0;i < E;i++)
		{
			StringTokenizer strtok = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(strtok.nextToken());
			int to = Integer.parseInt(strtok.nextToken());
			int weight = Integer.parseInt(strtok.nextToken());

			graph.get(from).add(new Edge(from, to, weight));
		}

		StringTokenizer strtok = new StringTokenizer(br.readLine());
		start = Integer.parseInt(strtok.nextToken());
		finish = Integer.parseInt(strtok.nextToken());

		dist = new int[V+1];

		//시작점만 0으로, 나머지까지 거리는 무한대
		for(int i = 0; i <= V;i++)
		{
			if(i != start)
				dist[i] = Integer.MAX_VALUE;
		}

		bw.write(dijkstra()+"");
	}

	static int dijkstra()
	{
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(start);

		visited[start] = true;

		while (!queue.isEmpty())
		{
			int now = queue.poll();

			//now에서 도달 가능한 정점들의 최단 거리 갱신
			for(int i = 0;i < graph.get(now).size();i++)
			{
				Edge e = graph.get(now).get(i);

				//이미 방문한 애들은 무조건 최단거리 (음수가 없다는 가정하의 다익스트라 특징)
				if(!visited[e.to])
					dist[e.to] = Math.min(dist[e.to], dist[now] + e.weight);
			}

			int next = getMinIndex();

			if(next != 0)
			{
				visited[next] = true;
				queue.offer(next);
			}
		}

		return dist[finish];
	}

	//만약 더이상 방문할 수 있는 노드가 없으면 0반환
	static int getMinIndex()
	{
		int min_index = 0;

		for(int i = 1;i <= V;i++)
		{
			if(!visited[i] && dist[min_index] > dist[i])
				min_index = i;
		}
		return min_index;
	}


	static class Edge{
		int from, to, weight;

		public Edge(int from, int to, int weight) {
			this.from = from;
			this.to = to;
			this.weight = weight;
		}
	}
	public static void main(String[] args) {
		try
		{
			solution();
			bw.close();
			br.close();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}

}