[Algorithm] 다익스트라

최단 경로 알고리즘

가장 짧은 경로를 찾는 알고리즘

 

보통 '길 찾기'에 많이 사용하는 알고리즘 이다.

최단 경로 알고리즘의 경우 보통 그래프로 표현하는데 각 지점은 그래프에서 노드로 표현되고, 지점 간 연결된 도로는 그래프에서 간선으로 표현된다.

주로 많이 사용 되는 최단 경로 알고리즘에는 밑에 3개가 있다.

• 다익스트라 최단 경로 알고리즘
• 플로이드 워셜
• 벨만 포드 

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

그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘

 

중요한 점은 음의 간선이 없을 때 정상적으로 동작한다.

• 음의 간선 : 0보다 작은 값을 가지는 간선

현실 세계에서의 길은 음의 간선으로 표현되지 않기 때문에 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘은 채택 되곤 한다.

 

원리 및 과정

1. 출발 노드를 설정

2. 최단 거리 테이블을 초기화

3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신

5. 3번과 4번을 반복!!

 

중요한 점은 '각 노드에 대한 현재까지의 최단 거리'정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다!!

다음과 같은 예시에서 출발 노드는 1이다.

초기 상태에서 다른 모든 노드로 가는 최단 거리를 '무한'으로 초기화 한다.

이때 Integer.MAX_VALUE 로 처리한다.

• 방문하지 않은 노드 중에서 최단 거리가 짧은 노드를 선택하는데, 출발 노드에서 출발 노드로의 거리는 0으로 본다.
  
  
  

  노드번호	1	2	3	4	5	6
  거리	0	무한	무한	무한	무한	무한

• 다음으로 1번 노드에서 다른 노드로 가는 비용을 계산한다. 즉 1번 노드와 연결된 모든 간선을 하나씩 확인한뒤 테이블을 갱신한다.

  노드 번호	1	2	3	4	5	6
  거리	0	2	5	1	무한	무한

• 다음 단계에서 최단 거리가 가장 짧은 노드를 선택하는데 여기서는
  4!! 4에서 갈 수 있는 노드인 3번과 5번 까지의 거리를 구하고 표를 다시 갱신한다.

  노드 번호	1	2	3	4	5	6
  거리	0	2	4	1	2	무한

• 다음 에서는 2번 노드가 선택된다.(거리가 같을 경우 일반적으로 번호가 작은 노드를 선택) 이전 단계와 동일한 방법을 반복한다. 

  노드번호	1	2	3	4	5	6
  거리	0	2	4	1	2	무한

• 결국 마지막의 테이블의 최종 갱신본은 다음과 같다.

  노드번호	1	2	3	4	5	6
  거리	0	2	3	1	2	4

이 테이블이 의미하는 바는 1번 노드에서 출발했을 때 2번, 3번, 4번, 5번, 6번 노드까지 가기 위한 최단 경로가 각각 2,3,1,2,4라는 의미다.

코드 구현

코드 구현을 위해서는 힙 자료구조를 사용한다.

힙 자료구조는 우선순위 큐를 구현하기 위하여 사용하는 자료구조중 하나인데 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징이다.

 

우선 순위 큐에서는 Node(값,비용) 으로 구성되며 가치가 낮은 데이터가 먼저 삭제되는 최소 힙, 가치가 높은 데이터가 먼저 삭제되는 최대 힙을 이용할 수 있다.

 

다익스트라 알고리즘을 구현할 때에도 이 우선순위 큐를 활용한다. 원리는 위의 설명과 동일하고 거리와 노드를 넣을 때 Node 클래스를 활용한다.

class Node implements Comparable<Node>{
	int index;
	int cost;
	
	public Node(int index, int cost){
		
		this.index = index;
		this.cost = cost;
    }

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

public static void Dijkstra(int n, int start){

	boolean[] check = new boolean[n+1];
	int[] dist = new int[n+1];
	
	int INF = Integer.MAX_VALUE;
	Arrays.fill(dist, INF);
	
	dist[start] = 0;
	PriorityQueue<Node> pq = new PriorityQueue<>();
	pq.offer(new Node(start, 0));
	
	while(!pq.isEmpty()){
		int nowVertex = pq.poll().index;
		
		if(check[nowVertex]) continue;
        
		check[nowVertex] = true;
		
		for(Node next : graph[nowVertex]){
			if(dist[next.index] > dist[nowVertex] + next.cost){
				dist[next.index] = dist[nowVertex] + next.cost;
				
				pq.offer(new Node(next.index, dist[next.index]));
			}
	}
	
	for(int i: dist){
		if(i == INF) System.out.print(0 + " ");
		else System.out.print(i+" ");
}

 

시간복잡도

인접 행렬로 표현 -> O(n^2)

우선순위 큐로 표현 -> O(ElogV)