다익스트라
다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.
출발 노드와 모든 노드 간의 최단 거리 탐색
에지는 모두 양수
O(ElogV) (노드 수 : V, 에지 수 : E)
dijkstra 알고리즘의 핵심 이론
인접 리스트로 그래프 구현하기
최단 거리 배열 초기화하기
값이 가장 작은 노드 고르기
최단 거리 배열 업데이트하기
과정 3~4를 반복하여 최단 거리 배열 완성하기
최단 경로 구하기
Question - 1753
Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class N56_P1753_최단_경로_구하기 {
public static int node, edge, start;
public static int distance[];
public static boolean visited[];
public static ArrayList<Edge> list[];
public static PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
node = Integer.parseInt(st.nextToken());
edge = Integer.parseInt(st.nextToken());
start = Integer.parseInt(br.readLine()); //주의 !!!!!!!!!11
distance = new int[node + 1];
visited = new boolean[node + 1];
list = new ArrayList[node + 1];
for (int i = 1; i <= node; i++) {
list[i] = new ArrayList<Edge>();
}
for (int i = 0; i <= node; i++) {
// 얘는 왜 0부터 해주는 거임 ?
distance[i] = Integer.MAX_VALUE; // 정수의 최댓값 출력
}
// u : 에서
// v : 로 가는
// w : 가중치
for (int i = 0; i < edge; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
list[u].add(new Edge(v, w));
}
pq.add(new Edge(start, 0));
distance[start] = 0;
while (!pq.isEmpty()) {
Edge current = pq.poll();
int CtoV = current.vertex;
if (visited[CtoV]) continue;
visited[CtoV] = true;
for (int i = 0; i < list[CtoV].size(); i++) {
Edge temp = list[CtoV].get(i);
int next = temp.vertex;
int value = temp.value;
if (distance[next] > distance[CtoV] + value) {
distance[next] = value + distance[CtoV];
pq.add(new Edge(next, distance[next]));
}
}
}
for (int i = 1; i <= node; i++) {
if (visited[i]) {
System.out.println(distance[i]);
} else {
System.out.println("INF");
}
}
}
}
class Edge implements Comparable<Edge> {
int vertex, value;
Edge(int vertex, int value) {
this.vertex = vertex;
this.value = value;
}
public int compareTo(Edge e) {
if (this.value > e.value) return 1;
else return -1;
}
}
jIdea
reference
최소 비용 구하기
Question - 1916
Code
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class N57_P1916_최소_비용_구하기 {
static int node, edge; // country, bus
static ArrayList<Node>[] list; // 인접 리스트로 그래프 표현하기
static int[] dist; //최단거리 배열 distance
static boolean[] visit; // 사용 노드인지 확인 visited
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
node = Integer.parseInt(br.readLine());
edge = Integer.parseInt(br.readLine());
dist = new int[node + 1];
visit = new boolean[node + 1];
Arrays.fill(dist, Integer.MAX_VALUE); // 거리 배열을 충분히 큰 수로 초기화
list = new ArrayList[node + 1]; //ArrayList<>[]아님 주의
for (int i = 0; i <= node; i++) { //또 채워줌 0
list[i] = new ArrayList<Node>();
}
for (int i = 0; i < edge; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int price = Integer.parseInt(st.nextToken());
list[start].add(new Node(end, price));
}
st = new StringTokenizer(br.readLine());
int startCountry = Integer.parseInt(st.nextToken());
int endCountry = Integer.parseInt(st.nextToken());
bw.write(dijkstra(startCountry, endCountry) + "\n");
bw.flush();
bw.close();
br.close();
}
public static int dijkstra(int start, int end) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start, 0));
dist[start] = 0;
while (!pq.isEmpty()) {
Node nowNode = pq.poll();
int now = nowNode.targetNode;
if (!visit[now]) {
visit[now] = true;
for (Node n : list[now]) {
if (!visit[n.targetNode] &&
dist[n.targetNode] > dist[now] + n.value) {
dist[n.targetNode] = dist[now] + n.value;
pq.add(new Node(n.targetNode, dist[n.targetNode]));
}
}
}
}
return dist[end];
}
}
class Node implements Comparable<Node> {
int targetNode;
int value;
Node(int targetNode, int value) {
this.targetNode = targetNode;
this.value = value;
}
@Override
public int compareTo(Node o) {
return value - o.value;
}
}
Idea
reference
K번째 최단 경로 찾기
Question - 1854
Code
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class N58_P1854_K번째_최단_경로_찾기 {
static final int INF = 100000000;
public static void main(String[] args) throws IOException {
int node, edge, k;
int[][] w = new int[1001][1001];
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
node = Integer.parseInt(st.nextToken());
edge = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
PriorityQueue<Integer>[] distQueue = new PriorityQueue[node + 1];
Comparator<Integer> cp = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 < o2 ? 1 : -1;
}
};
for (int i = 0; i < node + 1; i++) { // node + 1
distQueue[i] = new PriorityQueue<Integer>(k, cp);
}
for (int i = 0; i < edge; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
w[a][b] = c;
}
PriorityQueue<tNode> pq = new PriorityQueue<>();
pq.add(new tNode(1, 0));
distQueue[1].add(0);
while (!pq.isEmpty()) {
tNode u = pq.poll();
for (int adjNode = 1; adjNode <= node; adjNode++) {
if (w[u.node][adjNode] != 0) {
// 저장된 경로가 k개 안될 떄는 그냥 추가
if (distQueue[adjNode].size() < k) {
distQueue[adjNode].add(u.cost + w[u.node][adjNode]);
pq.add(new tNode(adjNode, u.cost + w[u.node][adjNode]));
}
// 저장된 경로가 k개이고, 현재 가장 큰 값보다 작을 때만 추가
else if (distQueue[adjNode].peek() > u.cost + w[u.node][adjNode]) {
distQueue[adjNode].poll();
distQueue[adjNode].add(u.cost + w[u.node][adjNode]);
pq.add(new tNode(adjNode, u.cost + w[u.node][adjNode]));
}
}
}
}
for (int i = 1; i <= node; i++) {
if (distQueue[i].size() == k) {
bw.write(distQueue[i].peek() + "\n");
} else {
bw.write(-1 + "\n");
}
}
bw.flush();
bw.close();
br.close();
}
}
class tNode implements Comparable<tNode> {
int node;
int cost;
tNode(int node, int cost) {
this.node = node;
this.cost = cost;
}
@Override
public int compareTo(tNode o) {
return this.cost < o.cost ? -1 : 1;
}
}
Idea
reference
Last updated
