정점 개수, 간선 개수가 주어지고,
그 이후로는 (시작노드, 도착노드, 가중치)가 간선의 개수만큼 주어진다.
시작노드에서 자신을 포함한 모든 노드까지의 최단 경로값을 출력한다. 이때 만약 시작노드에서 갈 수 없는 노드라면 INF로 출력한다.
최단 경로 알고리즘은 크게 세 가지이다. + bfs
각각 알고리즘의 상세는 다른 포스트에 정확히 정리하고자 한다.
각 알고리즘을 사용하는 상황은 다음과 같다.
1. 다익스트라 알고리즘
: 가중치가 모두 양수인 경우, 한 노드에서 다른 노드까지의 최단 경로, 최단 거리를 찾기에 용이하다.
2. 벨만-포드 알고리즘
: 가중치에 음수도 있을 경우에, 한 노드에서 다른 노드까지의 최단 경로, 최단 거리를 찾기에 용이하다. 이때 음의 사이클이 존재하는지도 파악 가능!
3. 플로이드-워셜 알고리즘
: 노드끼리의 전체 쌍에 대해 모든 최단 경로를 찾기에 용이하다.
그림으로 이해해보자
주요 메커니즘은 각 정점을 한 번씩만 들어간다는 것이다.
각 정점에 다다르면 해당 정점이 출발 정점인 간선을 찾아 최단 거리를 갱신하도록 한다. 이때 최단 거리가 갱신이 된다면 도착 정점과 cost를 min heap에 넣어준다.
min heap에서 또 하나의 원소를 꺼내서 해당 정점을 돌아보고, 최단 거리를 갱신하고, 다른 원소를 추가하고...
이렇게 min heap이 빌 때까지 반복하면 된다.
import java.io.*;
import java.util.*;
//도착 노드와 가중치를 저장하는 class 이다.
class Data2{
int to; long cost;
public Data2(int to,long cost) {
this.to = to;
this.cost = cost;
}
}
public class Main {
public static ArrayList<ArrayList<Data2>> aL; //인접리스트
public static long[] result; // 결과값
public static boolean[] visit; // 방문 여부
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String str = br.readLine();
String []sp = str.split(" ");
int V = Integer.parseInt(sp[0]); //정점의 개수
int E = Integer.parseInt(sp[1]); //간선의 개수
str = br.readLine();
int start = Integer.parseInt(str); //시작 노드
//인접 리스트 초기화
aL = new ArrayList<>();
for(int i = 0; i<=V;i++)
aL.add(new ArrayList<Data2>());
for(int i = 0; i<E;i++) {
str = br.readLine();
sp = str.split(" ");
// a->b (cost : c)
int a = Integer.parseInt(sp[0]);
int b = Integer.parseInt(sp[1]);
int c = Integer.parseInt(sp[2]);
aL.get(a).add(new Data2(b,c));
}
// 음의 가중치는 가지지 않고,
// 한 정점에서의 각 정점까지의 최단 거리를 구하는 것이므로
// 다익스트라 알고리즘을 사용하면 된다.
//결과 list 초기화, 방문 정보 초기화
result = new long[V+1];
visit = new boolean[V+1];
for(int i = 0; i<V+1;i++) result[i] = Integer.MAX_VALUE;
result[start] = 0;
//다익스트라 실행
Dijkstra(start);
//결과 출력
for(int i = 1; i<=V;i++) {
if(result[i] == Integer.MAX_VALUE) {bw.write("INF"+"\n"); continue;}
bw.write(result[i]+"\n");
}
bw.flush();
}
public static void Dijkstra(int v) {
//cost 기준으로 정렬하는 우선순위 큐 (min heap) 생성
PriorityQueue<Data2> q = new PriorityQueue<>(new Comparator<Data2>() {
@Override
public int compare(Data2 a,Data2 b) {
if(a.cost > b.cost) return 1;
else if(a.cost < b.cost) return -1;
else return 0;
}
});
//시작 노드와 시작노드-시작노드의 cost인 0을 넣는다.
q.add(new Data2(v,0));
while(!q.isEmpty()) {
Data2 tmp = q.poll(); //q에서 하나를 꺼낸다.
//꺼낸 data 확인
int to = tmp.to;
if(visit[to]) continue; //이미 방문했다면 pass
visit[to] = true; //정점을 방문했음을 표시
//꺼낸 node와 연결되어있는 간선을 체크한다.
for(int i = 0; i<aL.get(to).size();i++) {
Data2 next = aL.get(to).get(i);
//이 방향으로 오는게 원래 저장되어있던 최소 cost값보다 작다면
//이 경로로 오는 것이 더 최단 거리이다. --> 갱신
if(result[next.to] > result[to]+next.cost) {
result[next.to] = result[to]+next.cost;
q.add(new Data2(next.to,result[next.to])); //힙에 추가
}
}
}
}
}
다익스트라 알고리즘은 정말 정말 많이 쓰이는 최단 거리 알고리즘 이다.
최단 거리 알고리즘은 크게 3가지로 나뉘며, 각 알고리즘의 쓰임을 잘 알고 쓰자.
다익스트라 알고리즘이 기억이 안나면 ?
다익스트라 ==> min heap을 쓰는 bfs 정도로만 기억하자!