알고리즘(アルゴリズム）/자주 까먹는 알고리즘(よく忘れるアルゴリズム）
다익스트라 알고리즘
JIN_YOUNG _KIM
2023. 6. 15. 09:10
다익스트라 알고리즘은 최소 비용 신장 트리(MST)와는 달리
방향 그래프만 아니라, [무방향] 그래프에서도 적용이 가능하다.
import java.io.*;
import java.util.*;
public class Main {
private static final int INF = 10000;
//다익스트라 최단 경로
// 1. 하나의 시작 정점을 두고, 다른 모든 정점을 목적지로 하여 최단 경로를 구하는 것이다
// -> 모든 정점을 시작점으로 두고, 다른 모든 정점까지의 최단 경로는 [플로이드-워샬] 알고리즘으로 구한다.
// 2. 가중치가 있는 가중치 그래프를 전제로 한다.(가중치가 없으면, BFS로 최단 경로 구하면 됨)
// -> 시작 노드에서 목적지 노드까지의 가중치의 합이 최소인 경로가 최단 경로이다.
// 3. 인접 행렬을 이용한다.
// 인접 행렬
private static int weight[][] = { {0,10,5,INF,INF},
{INF,0,2,1,INF},
{INF,3,0,9,2},
{INF,INF,INF,0,4},
{7,INF,INF,6,0}};
private static int distance[] = new int[5];
private static HashSet<Integer> hashset = new HashSet<>();
public static void main(String[] args) {
// 1. 인접 행렬을 만든다.
// -> 인접 노드가 아니면, 0이 아닌 무한대(EX.Integer.MAX_VALUE..)를 삽입
// -> 인접 행렬의 대각선은 무조건 0이여야 한다.(노드 자기 자신이 시작 노드이자 목적지 노드라고 생각하면 왜 0이여야 하는지 납득이 갈 것이다)
// 2. 집합 (S)를 만든다(집합 S의 노드들은 이미 최단 경로가 확정된 노드들의 집합이라고 생각하면 편안~!)
// -> 최단 경로의 길이가 확정된 노드를 표시하기 위함!(집합 S에 모든 노드들이 다 저장이 되면 다익스트라 알고리즘이 종료)
// 3. distance 배열을 만든다
// -> 만약 {A,B,C}라는 노드 3개가 있는 가중치 그래프이고, 시작 노드를 A라고 했을 때,
// -> distance[0] = 인접행렬[A][A], distance[1] = 인접행렬[A][B], distance[2] = 인접행렬[A][C]로 초기화를 하며
// -> 이 distance의 값들을 집합(S)에 포함되지 않은 노드 중, 경로의 길이가 가장 짧은 노드를 집합(S)에 포함시켜서,
// -> 그 노드 이외에 다른 목적지 노들들이 만약 해당 노드를 경유하여 가는 경우가 더 경로가 짧아 진다면
// -> ditance의 값을 갱신을 하고, 경로가 같거나 더 길어지면 갱신을 하지 않는다.
// 0노드를 시작 노드라고 하자(나머지 노드들은 전부 목적지 노드가 된다)
for(int x = 0;x < 5; x++)
distance[x] = weight[0][x];
hashset.add(0);
distra(0);
System.out.println("123");
}
static void distra(int startNode){
for(int count = 0; count < 5-1;count++) {
int nextNode = nextShortestNode();
hashset.add(nextNode);
// nextNode를 경유하는 경우(distance[nextNode] + weight[nextNode][목적지 노드])와 경유하지 않는 경우(distance[목적지 노드])를 비교!
for (int x = 0; x < 5; x++) {
if (hashset.contains(x) == false) {
int case1 = distance[nextNode] + weight[nextNode][x];
int case2 = distance[x];
if (case1 < case2)
distance[x] = case1;
}
}
}
}
static int nextShortestNode(){
int min = Integer.MAX_VALUE;
int min_node = -1;
for(int x = 0; x < 5; x++){
if(hashset.contains(x) == false){
if(min >= distance[x]) { // min_node가 -1이 반환되지 않게 "="을 붙여줘야함
min = distance[x];
min_node = x;
}
}
}
return min_node;
}
}
아래와 같이 [인접 리스트]와 [우선 순위 큐]를 이용하여 구할 수도 있다.(백준 다익스트라 문제 참고)
import java.io.*;
import java.util.*;
public class Main {
private static final int INF = 3000001;
private static int v,e,start_node;
//인접 리스트를 이용한 다익스트라!
private static LinkedList<int[]> list[];
private static PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
private static int distance[];
private static int set[];
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine()," ");
v = Integer.parseInt(st.nextToken());
e = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine(),"");
start_node = Integer.parseInt(st.nextToken());
list = new LinkedList[v+1];
for(int x = 0; x <= v;x++)
list[x] = new LinkedList<>();
distance = new int[v+1];
set = new int[v+1];
for(int x = 0; x < e; x++){
st = new StringTokenizer(br.readLine());
int row = Integer.parseInt(st.nextToken());
int column = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
//방향 그래프
list[row].add(new int[]{column,w});
}
dikstra(start_node);
for(int x = 1; x <= v;x++) {
if(distance[x] != INF)
sb.append(distance[x]).append("\n");
else
sb.append("INF").append("\n");
}
System.out.println(sb);
}
static void dikstra(int start_node){
for(int x = 1; x <= v;x++)
distance[x] = INF;
distance[start_node] = 0;
pq.add(new int[]{start_node,0});
while (pq.isEmpty() != true) {
int[] next = pq.poll(); // 여기서 [poll() 되는 노드]는 최단 경로가 확정이 된 노드이다.
int node = next[0];
int weight = next[1];
for(int temp[]:list[node])
{
int nnode = temp[0];
int ncost = temp[1];
if(distance[nnode] > weight + ncost)
{
distance[nnode] = weight + ncost;
pq.add(new int[]{nnode,distance[nnode]}); // 갱신이 된 노드를 저장!
}
}
}
}
}