다익스트라를 사용하는 이유

BFS 사용 시, 격자 모양의 미로에서는 상하좌주 방향의 가중치가 모두 동일하였음

• 현재 위치에서 위로 가나 밑으로 가나 양옆으로 가나, 시간이 더 들거나 하지 않았음

• 현재 정점에서 이어진 간선들의 가중치가 모두 동일

만약, 가중치가 모두 일정하지 않다면? → BFS를 사용할 수 없음

다익스트라(Dijkstra)

한 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘

간선의 가중치가 양수일 때만 사용 가능

• 음수면, 다익스트라가 아닌 다른 알고리즘을 사용해야 함

BFS와 유사하지만, 다른 점은 일반적인 큐가 아닌 우선순위 큐(Priority Queue)를 사용하여, 비용이 가장 작은 간선으로부터 탐색한다는 점에서 차이가 있음

또한, BFS와 달리 가중치가 서로 다른 그래프도 처리 가능

다익스트라 알고리즘의 동작 순서

1. 출발 노드 선택

2. 출발 노드로부터 각 노드까지의 최단 거리 배열 초기화

• 초기에 출발 노드까지의 거리는 0이고, 나머지 노드는 무한대로 설정

3. 현재 노드 설정

• 현재까지 최단 거리가 확정되 논드 중 가장 가까운 노드 선택

4. 이웃 노드 갱신

• 선택한 노드를 기준으로 해당 노드와 이웃한 노드들 간의 거리 갱신

5. 모든 노드를 확인할 때까지 3단계와 4단계를 반복

다익스트라 알고리즘의 핵심 아이디어는 각 노드까지의 현재까지 알려진 최단 거리를 계속 업데이트하면서 출발 노드로부터 최단 경로를 찾는 것

다익스트라 알고리즘은 그리디(greedy) 알고리즘으로 분류되며, 매 단계에서 현재까지의 부분해(solution)를 최적화하여 최종적으로 전체 문제의 최적 해를 찾아냄

비용이 가장 작은 간선부터 이어주는 것이 우선순위 큐를 사용하는 이유라고 할 수 있음

시간 복잡도: $O(ElogV)$ (우선순위 큐)

다익스트라 알고리즘 구현

1. 출발 노드 선택

방향 그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로의 비용을 구하여라. 첫째 줄에 정점의 개수와 간선의 개수가 입력되고, 둘째 줄에는 시작 정점의 번호가 입력된다. 셋째 줄부터 간선의 개수만큼의 줄에 걸쳐 ($u$, $v$, $w$)가 주어진다. ($u$, $v$, $w$)는 $u$에서 $v$로 가는 양의 가중치 $w$인 간선이 존재한다는 뜻이다.

graph = (i: [] for i in range(1, N+1))

for _ in range(M):
	a, b, c = map(int, input().split())
    graph[a].append((b, c));

priority_queue = [(0, start)]

List<List<Pair>> graph = new ArrayList<>();

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

for (int i = 0; i < M; i++) {
	int a = scanner.nextInt();
    int b = scanner.nextInt();
    int c = scanner.nextInt();
    graph.get(a).add(new Pair(c, b));
}

PriorityQueue<Pair> priorityQUeue = new PriorityQueue<>();
priorityQueue.add(new Pair(0, st));

vector<pair<int, int>> v[20001];
for (int i = 0; i < M; ++i) {
	int a, b, c;
    cin >> a >> b >> c;
    v[a].push_back({b, c});
}
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
pq.push({0, st});

2. 출발 노드로부터 각 노드까지의 최단 거리 배열 초기화

초기에 출발 노드까지의 거리는 0이고, 나머지 노드는 무한대로 설정

distances = {vertext: sys.masxize for vertex in graph}
distacnes[start] = 0

long[] dist = new long[n+1];
Arrays.fill(dist, Long.MAX_VALUE);
dist[st] = 0;

long long dist[20001];
fill(dist, dist + 20001, INT_MAX);
dist[st] = 0;

3. 현재 노드 설정

현재까지 최단 거리가 확정되 노드 중 가장 가까운 노드 선택

4. 이웃 노드 갱신

선택한 노드를 기준으로 해당 노드와 이웃한 노드들 간의 거리 갱신

5. 모든 노드를 확인할 때까지 3단계와 4단계를 반복

while priority_queue:
	current_distance, current_vertext = heapq.heappop(priority_queue)
    
    if current_distance > distances[current_vertex]:
    	continue

	for neighbor, weight in graph[current_vertex]:
    	distance = current_distance + weight
        
		if distance < distance[neighbor]:
    		distance[neighbor] = distance
        	heapq.heappush(priority_queue, (distance, neighbor))

while (!priorityQueue.isEmpty()) {
	Pair current = priorityQueue.poll();
    long currentDistance = current.distance;
    int currentVertex = current.vertex;
    
    if (currentDistance > dist[currentVertex]) {
    	continue;
	}
    
    for (Pair neighbor : graph.get(currentVertex) {
    	long distance = currentDistance + neighbor.distance;
        
        if (distance < dist[neighbor.vertex]) {
        	dist[neighbor.vertex] = distance;
            priorityQueue.add(new Pair(distance, neighbor.vertex));
        }
    }
}

while (!pq.empty()) {
	int cost = pq.top().first;
    int now = pq.top().second;
    pq.pop();
    if (dist[now] < cost) {
    	continue;
	}
    for (auto&[next, nextCost]: v[now]) {
    	if (dist[next] > cost + nextCost) {
        	dist[next] = cost + nextCost;
            pq.push({dist[next], next});
		}
	}
}