Dijkstra 다익스트라 (최단 경로 알고리즘)

최단경로 문제란?

• 두 노드를 잇는 가장 짧은 경로를 찾는 문제이다
• 가중치 그래프(Weighted Graph)에서 간선(Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적

최단 경로 문제 종류

1. 단일 출발 및 단일 도착 (single-source and single-destiantion sortest path problem) 최단 경로 문제
   • 그래프 내의 특정 노드 u에서 출발, 또다른 특정 노드 v에 도착하는 가장 짧은 경로를 찾는 문제
2. 단일 출발 (single-source shortest path problem) 최단 경로 문제
   • 그래프 내의 특정 노드 u와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제
   • a와 연결된 b,c,d,e 중에서 가장짧은 경로를 찾는 것
3. 전체 쌍 (all-pair) 최단 경로 : 그래프 내의 모든 노드 쌍 (u, v)에 대한 최단 경로를 찾는 문제

최단 경로 알고리즘

다익스트라 알고리즘

• 단일 출발 최단 경로 문제(2번)를 위한 알고리즘
• 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 문제

로직

• 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법
• 너비우선탐색(BFS)와 유사하다
  • 첫 정점부터 각 노드간의 거리를 저장하는 배열을 만든 후, 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서, 첫 정점부터 해당 노드간의 가장 짧은 거리를 해당 배열에 업데이트
• 우선순위 큐를 사용한다

우선 순위 큐를 활용한 다익스트라 알고리즘

• 우선 순위 큐는 MinHeap방식을 활용해서 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내게 된다

1. 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장
   • 초기에는 첫 정점(시작정점)의 거리는 0, 나머지는 무한대로 저장한다(inf라고 표현)
   • 우선순위 큐에 (첫 정점, 거리 0)만 먼저 넣는다
2. 우선순위 큐에서 노드를 꺼낸다
   • 처음에는 첫 정점만 저장되어 있으므로, 첫 정점이 꺼내진다
   • 첫 정점에 인접한 노드들 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 정점에서 각 정점까지의 거리(현재 inf)를 비교한다
   • 배열에 저장되어 있는 거리보다, 첫 정점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트한다
   • 배열에 해당 노드의 거리가 업데이트 된 경우, 우선순위 큐에 넣는다
3. 2번 과정을 우선순위 큐가 비어있을때까지 반복한다

예제

1단계 _ 초기화

첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장

• 초기에는 첫 정점의 거리는 0, 나머지는 inf(무한대)로 저장
• 우선순위 큐에 (첫 정점, 거리(0))만 넣는다
  

2단계 (루프 시작)

우선순위 큐에서 추출한 (A, 0)노드인 첫 노드와의 거리를 기반으로 인접한 노드와의 거리 계산

• 우선순위 큐에서 노드를 꺼낸다
  • 처음에는 첫 정점만 저장되어 있으므로, 첫 정점(A, 0)이 꺼내진다
  • 첫 정점에 인접한 노드들 각각에 대해, 첫 정점과 각 노드간의 거리와 현재 배열에 저장되어있는 첫 정점과 각 노드간의 거리를 비교해준다 (실제거리 vs INF)
  • 배열에 저장되어 있는 거리보다, 첫 정점에서 해당 노드로 가는 거리가 짧으면, 배열에 해당 노드의 거리를 변경 해준다
  • 배열에 해당 노드의 거리가 변경된 경우, 우선 순위 큐에 넣어준다
    

3단계

우선순위 큐에서 (C, 1) 노드인 첫 노드와의 거리를 기반으로 인접한 노드와의 거리 계산

• 우선순위 큐가 MinHeap 방식이므로, 위 표에서 넣어진 (c,1), (d,2), (b,8)중 (c,1)이 먼저 추출된다
• 현재 배열에서 a-b의 거리는 8이다
  • 그런데 새로운 노드 기준으로 a-c의 거리는 1, c에 인접한 b노드까지의 거리는 5이므로 a-c-b의 거리는 1+5(6)이 된다. 따라서, 8보다 작으므로 배열에 업데이트를 하고 (b, 6)을 우선순위 큐에 넣어준다
  • 반대로, c-d의 거리는 2이고 a-c의 거리는 1로 a-c-d는 3인 반면 a-d는 2이므로 더 큰 경우에 해당해서 넣지 않고 무시된다

이런식으로 계속 새로운 인접노드를 확인하고 배열을 최소거리로 업데이트 해주면서 반복해준다
큐에서 꺼낸 노드의 비용이 배열에 적혀있는 비용보다 크거나 같다면 비교할 필요도없이 스킵하면된다

• 큐에서 꺼낸 노드까지 가는데 비용 >= 배열에 존재하는 노드까지의 비용 -> 계산 없이 스킵

구현

배열을 이용한 구현

Graph g = new Graph(8);
g.input(1, 2, 3);
g.input(1, 5, 4);
g.input(1, 4, 4);
g.input(2, 3, 2);
g.input(3, 4, 1);
g.input(4, 5, 2);
g.input(5, 6, 4);
g.input(4, 7, 6);
g.input(7, 6, 3);
g.input(3, 8, 3);
g.input(6, 8, 2);
g.dijkstra(1);

class Graph
{
	private int N;
	private int[][] maps;

	public Graph(int n)
	{
		this.N = n;
		maps = new int[N+1][N+1];
	}

	public void input (int i, int j, int w)
	{
		maps[i][j] = w;
		maps[j][i] = w;
	}

	public void dijkstra(int v)
	{
		int[] distances = new int[N+1];
		boolean[] visited = new boolean[N+1];

		for (int i = 1; i < N+1; i++)
			distances[i] = Integer.MAX_VALUE;

		distances[v] = 0;
		visited[v] = true;

		for (int i = 1; i < N+1; i++)
		{
			if (!visited[i] && maps[v][i] != 0) //방문했고 0이 아니라면 (방문했으면 무한값은 아니다)
				distances[i] = maps[v][i];
		}

		for (int all = 0; all < N-1; all++)
		{
			int min = Integer.MAX_VALUE;
			int min_idx = -1;

			for (int i = 1; i < N+1; i++) {
				if (!visited[i] && distances[i] != Integer.MAX_VALUE) {
					if (distances[i] < min){
						min = distances[i];
						min_idx = i;
					}
				}
			}
			visited[min_idx] = true;

			for (int i = 1; i < N+1; i++) {
				if (!visited[i] && maps[min_idx][i] != 0){
					if (distances[i] > distances[min_idx] + maps[min_idx][i])
					{
						distances[i] = distances[min_idx] + maps[min_idx][i];
					}
				}
			}
			for (int i = 1; i < N+1; i++)
				System.out.print(distances[i] + " ");
			System.out.println();
		}
	}
}

Priority Queue를 이용한 구현

public class Dijkstra_algorithm {
    public static void main(String[] args) throws IOException {
        Dijkstra_pq(0);
    }

    private static void Dijkstra_pq(int start) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        List<Edge>[] adj = new ArrayList[V];
        for (int i = 0; i  < V; i++)
            adj[i] = new ArrayList<>();

        //간선의 출발, 도착, 가중치를 읽어들여서 그래프의 연결상태를 저장
        for (int i = 0; i < E; i++) {
            //출발 노드, 도착 노드, 가중치
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            int weigth = Integer.parseInt(st.nextToken());
            adj[from].add(new Edge(dest, weigth));
        }

        //우선순위 큐, 방문 체크
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        boolean[] check = new boolean[V];

        //첫노드로부터의 모든 노드들의 거리배열
        Edge[] D = new Edge[V];
        //배열중 출발 노드만 거리가 0 나머지는 최대값으로 설정
        for (int i = 0; i < V; i++){
            if (i == start)
                D[i] = new Edge(i, 0);
            else
                D[i] = new Edge(i, Integer.MAX_VALUE);
        }
        //우선순위큐에 시작 노드를 넣고 시작
        pq.add(D[start]);
        while (!pq.isEmpty())
        {
            //우선순위 큐에 가장 위에있는 노드 및 가중치를 가져온다
            Edge nowV = pq.poll();
            //edge.v에 연결되어있는 간선 리스트를 가져온다
            for (Edge nextV : adj[nowV.v]){
                //시작노드부터 다음 노드에 대한 기존 가중치보다 지금까지의 경로 + 다음 노드로의 경로 가중치 합이 더 작다면 변경
                if (!check[nextV.v] && D[nextV.v].weight > D[nowV.v].weight + nextV.weight) {
                    D[nextV.v].weight = D[nowV.v].weight + nextV.weight;
                    pq.add(D[nextV.v]);
                }
            }
            check[nowV.v] = true;
        }
        System.out.println(Arrays.toString(D));
    }
}

class Edge implements Comparable<Edge> {
    int v, weight;

    public Edge(int v, int weight) {
        this.v = v;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge o) {
        return Integer.compare(this.weight, o.weight);
    }

    @Override
    public String toString() {
        return weight + " ";
    }
}

• 입력
  4 5
  0 1 2
  0 2 3
  1 3 1
  0 3 5
  1 2 1

• 출력
  [0 , 2 , 3 , 3 ]

시간 복잡도

과정

1 각 노드마다 인접한 간선들을 모두 검사하는 과정
2 우선순위 큐에 노드/거리 정보를 넣고 삭제(poll)하는 과정

과정 1 시간복잡도

각 노드는 최대 한 번씩 방문하므로(첫노드와 해당노드간 길이 있다면), 최대 그래프의 모든 간선의 개수인 O(E)이다

과정 2 시간복잡도

우선순위 큐에 가장 많은 (노드, 거리)정보가 들어가는 경우는 그래프의 모든 간선이 검사 될 때마다, 배열의 최단 거리가 변경되고, 우선순위 큐에 (노드, 거리)가 추가되는 경우이다
따라서, 이 때 추가는 간선마다 최대 한번씩 일어날 수 있으므로 최대 O(E)의 시간이 소요되며, O(E)개의 (노드, 거리)정보에 대해 우선순위 큐를 유지하는 작업은 MinHeap유지시간인 O(logE)가 걸린다
결론적으로 O(E * logE) 이다

과정1 + 2의 시간복잡도가 소요되고 O(ElogE)의 시간이 소요된다