Dijkstra - 데이크스트라(다익스트라)

데이크스트라(Dijkstra)는 BFS 알고리즘을 알고 있다면 조금 더 쉽게 이해할 수 있다.

시작 지점 부터 가고자하는 도착지점까지 최소한의 시간으로 도착할 수 있는 거리를 구하는 알고리즘이다.

 

ex)https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

예제 입력은 1번에서 출발하여 5번까지 도착하는데 걸리는 최소 시간을 구하는 문제입니다.

1 -> 4 -> 5을 이동하게 된다면 1 + 3 = 4의 시간이 걸리게 됩니다.

 

<JAVA>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int n;
	static int[] dist;
	static List<Node>[] list;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		
		dist = new int[n + 1];
		list = new ArrayList[n + 1];
		
		Arrays.fill(dist, Integer.MAX_VALUE); // 현재 안간 노드들을 모두 최대시간 소요된다고 가정
		
		for(int i = 1; i <= n; i++) {
			list[i] = new ArrayList<>();
		}
		
		while(m --> 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			
			list[a].add(new Node(b, cost));
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		System.out.print(dijkstra(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
	}
	
	public static int dijkstra(int start, int end) {
		PriorityQueue<Node> queue = new PriorityQueue<>();
		queue.add(new Node(start, 0)); // 출발위치, 소요 시간 저장
		dist[start] = 0; // 출발 노드의 소요시간은 0
		
		while(!queue.isEmpty()) {
			Node now = queue.poll();
			
			if(dist[now.to] < now.weight) {
				continue;
			} // 현재까지 소요되는 최소시간이 지나온 거리의 길이보다 작으면 pass
				
			for(Node node : list[now.to]) {
				if(dist[node.to] > dist[now.to] + node.weight) {
					dist[node.to] = dist[now.to] + node.weight;
					queue.add(new Node(node.to, dist[node.to]));
				}//다음에 갈 노드까지의 최소시간이 현재 노드까지 걸린 시간 + 다음 노드까지의 거리보다 작으면 change
			}
		}
		return dist[end];
	}
}

class Node implements Comparable<Node>{
    int to, weight;

    public Node(int to, int weight){
        this.to = to;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }// 소요되는 시간을 기준으로 정렬
}

<C++>

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

vector<pair<int, int>> arr[1001];
int dist[1001];
int s, e;
int n, m;

void dijkstra() {
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, s });
	dist[s] = 0;

	while (!pq.empty()) {
		int weight = -pq.top().first;
		int cur = pq.top().second;
		pq.pop();

		if (dist[cur] < weight) {
			continue;
		}

		for (pair<int, int> next : arr[cur]) {
			int ncur = next.first;
			int nweight = next.second;

			if (dist[ncur] > dist[cur] + nweight) {
				dist[ncur] = dist[cur] + nweight;
				pq.push({ -dist[ncur], ncur });
			}
		}
	}\
}

int main()
{
	cin.tie(NULL)->sync_with_stdio(false);

	fill(dist, dist + 1001, 1e9);
	
	cin >> n >> m;

	int a, b, w;
	while (m--) {
		cin >> a >> b >> w;
		arr[a].push_back({ b, w });
	}
	
	cin >> s >> e;

	dijkstra();

	cout << dist[e];
}

 

추천 문제

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

https://www.acmicpc.net/problem/1753

1753번: 최단경로