[알고리즘] 다익스트라 알고리즘이란?!

코테 준비 뭐 얼마나 안했다고 걍 다까먹었다. 지금 당장 취업하지 않더라도 준비 해둬야지,,

---

📌 Dijkstra Algorithm(다익스트라 알고리즘)이란?!

특정 시작점에서 다른 모든 정점으로 가는 최단거리를 각각 구해주는 알고리즘
5개의 정점이 있고 1번 정점에서 출발할 때, 다른 2-5번의 정점으로 가는 최단거리를 구해줌

현재 나는 마을들을 돌아다니며 방문해야 하는 임무를 맡았다
이 상황에서 당장 A마을을 가는 최단거리는 확실히 알지만 다른 마을까지의 거리는 잘 모른다.
이때, A마을을 거쳐 다른 지점을 갈 수 있다면

➡️ 특정 지점까지의 거리 = A까지 가는 거리 + A에서 특정 지점까지 소요되는 거리

라고 할 수 있다!!

여기서 중요한건 A로의 최단거리를 알고, A를 거쳐 다른 지점에 갈 수 있다는거다.
물론 다른 경로에 최단거리가 있을 수는 있지만, 기억하자!

‼️나는 내가 있는 곳에서 이어진 마을이 아니면 이어져있지 않은 마을의 거리를 알지 못한다‼️

그림으로 살펴보자

출처: 코드트리

내가 현재 5번 마을에 있다고 가정해보자.
난 이어져있는 2, 4번 마을에 가는 법은 알지만, 1, 3번까지 얼마나 걸리는지는 알지 못한다.

따라서 당장 다음 마을로 이동해서, 가장 최단거리로 이어진 마을을 방문하는 것이 나의 목표이다!
그리디 알고리즘이랑 비슷한 느낌이라고 보면 좋을 것 같다.
현재 지금 상황에서 최선의 경로를 찾는걸 목표로 삼자!

---

📌 풀이방법

그럼 이제 수도코드와 함께 어떻게 푸는지를 알아봐야겠다.

🔍 초기 설정

function dijkstra(graph, source)
	set Q = Queue()
    
    for each vertex in graph
    	set dist[v] = INF
        Q.push(v)
        
    set dist[source] = 0

먼저 마을간의 관계는 그래프 형태로 저장되어 있고, 시작점을 선택해주어야 하므로 source가 존재한다.

1. dist 배열에 전부 INF 값을 넣어준다. 이때 배열의 위치는 각 정점을 의미한다!
   ex) dist[1] = (시작 정점에서 1번 정점까지의 거리)
2. 큐에 각 정점들을 넣어준다.
3. 마지막으로 시작점(source)까지의 거리는 0으로 초기화해준다
   당연함! 나에서 나로 가는 거리는 0이니까

🔍 이동 시작!

while Q is not empty
	set u = vertex in Q with min dist
    Q.remove(u)
    
    for each neighbor v of u
    	set alt = dist[u] + length(u, v)
        if alt < dist[v]
        	set dist[v] = alt

이제 이동을 시작해보겠다!

1. Q가 비어있는지 확인한다.
   Q는 현재 방문하지 않은 정점들이 저장되있다! 따라서 Q가 비어있으면 모든 정점을 방문했다는 의미기에 반복문을 탈출할 수 있다.
2. Q에 있는 정점들 중, 가장 짧은 거리값을 가지고 있는 정점을 뽑아 u를 초기화해준다.
   첫 이동시에는 당연히 0으로 초기화된 시작점이 뽑힐 것이다.
3. 가장 짧은 거리값을 가진 정점을 뽑았다는 것은 그 정점을 방문한다는 의미이다. 그렇기에 방문되지 않은 노드를 저장하는 Q에서는 해당 정점을 지워주어야 한다.
4. 이번엔 for문을 돌며 거리값을 계산해준다.
5. 방문하고 있는 정점인 u의 이웃들인 v들에 대해
   u의 이전 방문 위치에서의 거리값 + u에서 v까지의 거리값을 계산하고, 기존의 시작점에서 v까지의 거리값과 비교하여 더 작은 값으로 갱신해준다.

이부분 좀 헷갈릴 수도 있는데 (일단 난 헷갈렷음..)

시작 지점에서 특정 마을까지의 최단거리를 구하는거니까, 중간에 어떤 마을을 거치더라도! 더 작은 값이 나오면 갱신해주어야 한다는 것을 잊지 말자!

이 이미지를 보면, 5에서 바로 2로 가는 거리는 4이지만, 5에서 4를 거쳐 2로 가게 되면 거리가 3으로 줄어든다!

이런 예시가 존재하기에 5번 과정에서의 갱신이 무조건적으로 필요하다.

위의 과정을 Q가 빌때까지 반복하면, 최단 경로가 저장된 dist 배열이 만들어진다!

📌 시간복잡도?

알고리즘을 풀땐 시간복잡도도 굉장히 중요하다.
코테 이후 면접을 볼때 알고리즘의 시간 복잡도를 말해보라는 경우도 종종 있다고...

그래프 내의 정점의 수를 V, 간선의 수를 E라고 했을 때, 알고리즘의 시간 복잡도는 $O(ElogV)$ 가 된다!
그 이유는

각 간선을 한 번씩 봐야 하고, 이때 dist 값이 변하게 되면, 우선순위큐에서 순서가 계속 바뀌게 될 수 있음

➡️ 시간복잡도: 간선의 수 X 우선순위 큐

이때 위의 시간 복잡도를 가지기 위해선 그래프를 꼭 인접 리스트의 형태로 관리해주어야 한다.

🔍 인접리스트란?

V개의 동적 배열을 만들어서 그래프를 표현하는 방법

1. i번째 정점에 해당하는 동적 배열: graph[i]
2. graph[i]에 해당하는 동적 배열에 정점 i에 연결된 모든 정점 번호가 들어가야 함

공간 복잡도는 당연히, 정점의 수 V와 간선의 수 E를 합친 $O(V+E)$가 된다.

---

✨ 고려사항

😇 만약 간선의 값이 마이너스라면?! 다익스트라로 최단 경로를 구할 수 있을까?

불가능!! 위에서 말했지만,

➡️ 특정 지점까지의 거리 = A까지 가는 거리 + A에서 특정 지점까지 소요되는 거리

이다. 근데 A까지 가는 거리는 항상 최소값이라고 여기는 것이 이 알고리즘의 특징이다.
그런데 다른 마을로 이동하며, 마이너스 경로가 있게 되면, 다른 지점에서 A마을로 이동하는 값이 더 작은 경우가 앞으로 발생할 수 있다.

이 그래프를 보면, 5에서 시작했을 때 2로 이동하는 것이 최단이라서 이동했더니, 사실 5->4->2 가 최단이었다는 경우가 존재해버린다.

---

📌 최종 코드

아무래도! 최종 코드가 없으면 반쪽짜리 공부가 아닐까 싶다 ㅎ..ㅎ
자바로 준비중이기에 자바 코드로 첨부하겠다

import java.util.*;

class Edge{
	int x, y, weight;
    
    public Edge(int x, int y, int weight){
    	this.x = x;
        this.y = y;
        this.weight = weight;
    }
};

class Node{
	int index, dist;
    
    public Node(int index, int dist){
   		this.index = index;
        this.dist = dist;
    }
};

class Element implements Comparable<Element>
	int dist, index;
    
    public Element(int dist, int index){
    	this.dist = dist;
        this.index = index;
    }
    
    // dist 기준으로 오름차순으로 정렬!
    @Override
    public int compareTo(Element e){
    	return this.dist - e.dist;
    }
};

pulic class Main{

	// 이 값은 앞으로 주어지는 n의 값으로 변경해주면 된다!
	public static final int MAX_N = 5;
    
    // 인접 리스트 생성
    public static ArrayList<Node>[] graph = new ArrayList[MAX_N];
    
    // 우선순위 큐!
    public static PriorityQueue<Element> pq = new PriorityQueue<>();
    
    public static int[] dist = new int[MAX_N];
    
    public static void main(String[] args){
    	// 정점 5개, 간선 8개
    	int v = 5, e = 8;
        
        // 주어진 간선 정보 (x, y, weight)
        // x -> y로 향하는 간선이 있으며, 가중치는 weight
        Edge[] edges = new Edge[]{
            new Edge(-1, -1, -1),
            new Edge(2, 1, 3),
            new Edge(1, 4, 3),
            new Edge(4, 2, 1),
            new Edge(5, 2, 4),
            new Edge(5, 4, 2),
            new Edge(4, 3, 2),
            new Edge(3, 4, 1),
            new Edge(1, 3, 6)
        };
        
        // 그래프를 인접 리스트로 표현
        for(int i = 0 ; i < n; i++){
        	graph[i] = new ArrayList<>();
        }
        
        for(int i = 1; i <= m; i++) {
            int x = edges[i].x;
            int y = edges[i].y;
            int z = edges[i].z;
            graph[x].add(new Node(y, z));
        }
        
        // 그래프에 있는 모든 노드들에 대해
        // 초기값을 전부 아주 큰 값으로 설정
        // INT_MAX 그 자체로 설정하면
        // 후에 덧셈 진행시 overflow가 발생할 수도 있으므로
        // 적당히 큰 숫자로 적어줘야함에 유의!
        for(int i = 0; i<n; i++){
        	dist[i] = (int)1e9;
        }
        
        // 시작위치에는 dist값을 0으로 설정
        // 여기서는 5번이 시작위치
        dist[5] = 0;
        
        // 우선순위 큐에 시작점을 넣어줌, 여기선 5!
        // 해당 지점이 어디인지에 대한 정보도 필요하므로
        // (거리, 정점 번호) 형태로 넣어줘야 합니다.
        pq.add(new Element(0, 5));
        
        // O(|E|log|V|) 다익스트라 코드
        // 우선순위 큐에
        // 원소가 남아있다면 계속 진행해줍니다.
        while(!pq.isEmpty()){
        	// 가장 가까운 정보를 받아온 후, 원소 제거
            int minDist= pq.peek().dist;
            int minIndex = pq.peek().index;
            pq.poll();
            
            // 우선순위 큐를 이용하면
            // 같은 정점의 원소가 
            // 여러 번 들어가는 문제가 발생할 수 있어
            // minDist가 최신 dist[minIndex]값과 다르다면
            // 계산할 필요 없이 패스!!!!! ✨
            if(minDist != dist[minIndex])
                continue;
                
            // 최솟값에 해당하는 정점에 연결된 간선들을 보며
            // 시작점으로부터의 최단거리 값을 갱신해줍니다.
            for(int j = 0; j < graph[minIndex].size(); j++){
            	int targetIndex = graph[minIndex].get(j).index;
                int targetDist = graph[minIndex].get(j).dist;
                
                // 현재 위치에서 연결된 간선으로 가는 것이 더 작다면
                int newDist = dist[minIndex] + targetDist;
                if(dist[targetIndex] > newDist){
                	dist[targetIndex] = newDist;
                	pq.add(newDist, targetIndex);
                }
            }
        }
    }
}

저기 위에서

// 우선순위 큐를 이용하면
// 같은 정점의 원소가 
// 여러 번 들어가는 문제가 발생할 수 있어
// minDist가 최신 dist[minIndex]값과 다르다면
// 계산할 필요 없이 패스!!!!! ✨
if(minDist != dist[minIndex])
    continue;

이부분이 있다.
난 이 부분이 대체 왜 존재하나 했는데,,

• 큐에서 꺼낸 (minDist, minIndex) 쌍이 최신 최단 거리 정보를 반영하는지 확인
• minDist가 dist[minIndex]와 다르면, 이는 dist[minIndex]가 더 짧은 거리로 이미 업데이트되었음을 의미
• 따라서 현재 꺼낸 정보는 무시하고 다음으로 넘어감

이 이유 때문이다!
큐에 저장된 값은 이미 최솟값으로 업데이트 되어있다. 그리고 그 동일한 값으로 큐에도 저장되어있다. 그런데 값이 달라졌다는건, 이미 이전의 값이 더 작은 값이어서 업데이트를 안한 경우이다!!!!!!!!

따라서 건너뛰어야 한다 ㅎㅎ

---

후.. 겨우 다 정리했다. 아무래도 머리가 많이 굳기도 했고, 계속 제대로 공부 안하고 겉핥기로 하다보니 거의 3시간정도 걸린듯 ㅜㅜㅜㅜㅜ 분발하자!

출처

https://www.codetree.ai/missions/8/problems/shortest-path-to-each-vertex-3/introduction