🔎 개념
다익스트라 최단경로 알고리즘
:그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구하는 알고리즘. (양의 간선으로만 이루어져 있을때, 정상적으로 작동)
-
알고리즘
1) 출발 노드 설정
2) 출발점으로 부터 각 노드까지의 최단 거리 테이블 생성 및 최단거리로 무한한 값 설정,초기화
3) 방문하지 않은 노드 중에서 현재노드로부터 최단거리인 노드 선택
4) (기존 값보다 작다면)선택한 노드까지 거리로 최단거리 테이블값 갱신
5) 3,4번 반복 -
.✔ 2차원 ArrayList사용 : 특정 출발지점 a에 접근해 a와 연결된 다른 지점들과의 거리를 탐색하고 갱신해야하기에 각 노드에 대한 (연결된 다른 노드들, 그 노드까지의 최단 거리) 정보를 추가하는 작업 필요함
-
우선순위 큐를 이용한 다익스트라 구현
-- Node클래스 내 거리가 짧은 순으로 정렬이 되도록 compareTo() 오버라이딩을 함으로써
-- 우선순위 큐에 각 노드의 정보를 할당함에 따라 나중에 큐.poll()을 할때 가장 거리가 짧은 노드가 우선순위로 나오게 됨!
import java.util.*;
// 각 노드의 번호, 비용에 쉽게 접근하기위해 class 생성
class Node implements Comparable<Node>{
private int idx;
private int distance;
public Node(int idx, int distance) {
this.idx = idx;
this.distance = distance;
}
public int getIdx() {
return this.idx;
}
public int getDistance() {
return distance;
}
// 거리가 짧은 순으로 정렬(오름차순)
@Override
public int compareTo(Node o) {
return this.distance - o.distance;
}
}
public class Java0715_1 {
public static int n,m,start;
// n: 노드 갯수, m : 간선의 갯수, start : 노드 시작 번호
public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
public static int[] d = new int[100001]; // 최단거리 테이블 생성(노드 갯수가 100,000라고 가정)
// 1번 노드부터 100000번 노드까지 만들기위해 100001개 생성
public static final int INF = (int) 1e9;
// 무한을 의미하는 값, 10억 설정
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
start = sc.nextInt();
// 그래프 초기화
for(int i=0;i<n;i++) graph.add(new ArrayList<Node>());
// 모든 간선 정보(a노드에서 b노드로 가는 비용 c) 입력
for(int i=0; i<m;i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
graph.get(a).add(new Node(b,c));
}
// 최단거리 테이블 무한으로 초기화
Arrays.fill(d, INF);
dijkstra(start);
// 1번 ~ n번 노드로 가기위한 최단 거리 출력
for(int i=1; i<=n; i++) {
if(d[i] == INF) System.out.println("INFINITY");
else System.out.println(d[i]);
}
}
public static void dijkstra(int start) {
PriorityQueue<Node> pq = new PriorityQueue<>();
// 시작 노드이니까 (시작노드 번호, 거리=0)으로 시작
pq.offer(new Node(start,0));
d[start] = 0;
while(!pq.isEmpty()) {
Node node = pq.poll();
int distance = node.getDistance(); // 현재노드까지의 비용
int now = node.getIdx(); // 현재 노드 번호
// 현재 출발점에서부터 now노드 까지의 최단거리 테이블 값(d[now])보다
// 이전노드에서부터 now노드까지의 거리(distance)가 더 클 때는 무시
if(d[now] < distance) continue;
for(int i=0; i<graph.get(now).size();i++) {
int cost = d[now] + graph.get(now).get(i).getDistance();
// graph가 2차원 리스트이기에 테이블 원소에 접근하려면 get() 2번 사용해야함
// 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧으면 갱신해주기!
if(d[graph.get(now).get(i).getIdx()] > cost) {
d[graph.get(now).get(i).getIdx()] = cost;
pq.offer(new Node(graph.get(now).get(i).getIdx(),cost));
}
}
}
}
}플로이드 워셜 알고리즘
: 다익스트라와 달리 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 구하는 경우 사용
-
점화식 D(ab) = min(D(ab), D(ak)+ D(kb))을 이용함으로써 다이나믹 프로그래밍에 속함.
-
D(ab) = min(D(ab), D(ak)+ D(kb))
: a -> b 거리와 특정 지점 k를 거칠때 거리 a->k + k->b 비교 -
노드 500개 이하일 때 사용 권장
-
.✔ 2차원 배열 사용 : 특정 출발지점 a에 접근해 a와 연결된 다른 지점들, 그 지점과의 거리를 탐색하고 갱신하는 과정을 하는 다익스트라와 달리 모~든 지점사이의 최단거리를 구해야 하기에
모든 지점 중 두 개의 지점 a,b에 접근하여 그 사이 거리 c를 구하는 작업을 반복하기에 graph[a][b] =c로 저장만 하면 됨
import java.util.Arrays;
import java.util.Scanner;
public class Java0715_2 {
// 노드의 개수(N), 간선의 개수(M)
// 노드의 개수는 최대 500개라고 가정
public static int n,m;
public static int[][] graph = new int[501][501];
public static final int INF = (int) 1e9;
// 무한을 의미하는 10억
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
// 최단거리 테이블 모두 무한으로 초기화
for(int i=0;i<501; i++) {
Arrays.fill(graph[i], INF);
}
// 자기 자신 -> 자기 자신 의 거리는 0으로 설정해주기
for(int i=0; i<n;i++) {
for(int j = 0;j<n;j++)
{
if(i==j) graph[i][j] = 0;
}
}
// 각 간선에 대한 정보 입력받고 그값으로 초기화
for(int i=0; i<m; i++) {
// a에서 b로 가는 비용c
int a= sc.nextInt();
int b= sc.nextInt();
int c = sc.nextInt();
graph[a][b] = c;
}
// a와 b사이 걸쳐갈 지점 k
for(int k=1;k<=n;k++) {
for(int a = 1; a<=n;a++) {
for(int b=1;b<=n;b++) {
graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
}
}
}
for(int a =1;a<=n;a++) {
for(int b = 1;b<=n; b++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (graph[a][b] == INF) {
System.out.print("INFINITY ");
}
// 도달할 수 있는 경우 거리를 출력
else {
System.out.print(graph[a][b] + " ");
}
}
System.out.println();
}
}
}📚 전보 - 다익스트라 알고리즘
import java.util.*;
class Node implements Comparable<Node> {
private int idx;
private int distance;
public Node(int idx, int distance) {
this.idx = idx;
this.distance = distance;
}
public int getIdx() {
return this.idx;
}
public int getDistance() {
return this.distance;
}
@Override
public int compareTo(Node o) {
if(this.distance < o.distance) return -1;
return 0;
}
}
public class Java0715_3 {
public static int n,m,start;
public static int[] d= new int[30001]; // 도시의 개수 만큼 최단거리 테이브 생성
public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
public static final int INF = (int)1e9;
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
start = sc.nextInt();
for(int i=0;i<n;i++) graph.add(new ArrayList<Node>());
Arrays.fill(d, INF);
for(int i=0;i<m;i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
graph.get(a).add(new Node(b,c));
}
dijstra(start);
// 출발점으로부터 연결된 도시의 수
int cnt = 0;
// 도달한 도시 중, 가장 멀리있는 도시와의 거리
int maxDistance =0;
for(int i=1;i<=n;i++) {
if(d[i]!=INF) {
cnt++;
maxDistance = Math.max(maxDistance, d[i]);
}
}
System.out.print((cnt-1) +" " + maxDistance);
// 시작 노드제외 하기위해 cnt-1
}
public static void dijstra(int start) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start,0));
d[start] = 0;
while(!pq.isEmpty()) {
Node node = pq.poll();
int distance = node.getDistance();
int nowIdx = node.getIdx();
if(d[nowIdx] < distance) continue;
for(int i=0;i<graph.get(nowIdx).size();i++) {
int cost = d[nowIdx] + graph.get(nowIdx).get(i).getDistance();
if(cost < d[graph.get(nowIdx).get(i).getIdx()])
{
d[graph.get(nowIdx).get(i).getIdx()] = cost;
pq.offer(new Node(graph.get(nowIdx).get(i).getIdx(),cost));
}
}
}
}
}📚 미래도시 - 플로이드 워셜 알고리즘
: 도시간 거리가 1로 정해져 있고, 특정 지점을 거친 최소거리를 요구 + 노드수 100여개 -> 플로이드 워셜 알고리즘
import java.util.*;
public class Java0715_4 {
public static int n,m,x,k;
public static int[][] graph=new int[101][101];
public static final int INF = (int) 1e9;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for(int i=0;i<101;i++) Arrays.fill(graph[i], INF);
for(int i=1;i<=n;i++) {
for(int j=1; j<=n;j++) {
if(i==j) graph[i][j] =0;
}
}
for(int i=0;i<m;i++) {
int a = sc.nextInt();
int b = sc.nextInt();
graph[a][b] = 1;
graph[b][a] = 1; // 주의) 양방향 노드이기에!
}
x = sc.nextInt();
k = sc.nextInt();
for(int k=1;k<=n;k++) {
for(int a =1;a<=n;a++) {
for(int b =1;b<=n;b++) {
graph[a][b] = Math.min(graph[a][b],graph[a][k]+graph[k][b]);
}
}
}
int answer = graph[1][k] + graph[k][x];
if(answer >= INF) System.out.print(-1);
else System.out.print(answer);
}
}