가장 짧은 경로를 찾는 알고리즘
다영한 문제 상황이 있다
•
한 지점에서 다른 한 지점까지의 최단 경로
•
한 지점에서 다른 모든 지점까지의 최단 경로
•
모든 지점에서 다른 모든 지점까지의 최단 경로
다익스트라(dijkstra)
•
특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로
•
음의 간선이 없을 때 정상적으로 동작
•
매 상황에서 가장 비용이 적은 노드를 선택하므로 그리디 알고리즘으로 분류
•
인접 리스트
1.
출발 노드 설정
2.
최단 거리 테이블 초기화
3.
방문하지 않은 노드중에서 최단 거리가 가장 짧은 노드를 선택
4.
해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
다익스트라 알고리즘 구현 - 간단한 구현 방법
import java.sql.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
class Node {
private int index;
private int distance;
public Node(int index, int distance) {
this.index = index;
this.distance = distance;
}
public int getIndex() {
return this.index;
}
public int getDistance() {
return this.distance;
}
}
public class 다익스트라간단구현 {
public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억 설정
public static int n, m, start;
public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
public static boolean[] visited = new boolean[100001];
public static int[] d = new int[100001];
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>());
}
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);
// 모든 노드로 가기 위한 최단 거리를 출력
for (int i = 1; i <= n; i++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (d[i] == INF) {
System.out.println("INFINITY");
}
// 도달할 수 있는 경우 거리를 출력
else {
System.out.println(d[i]);
}
}
}
private static void dijkstra(int start) {
d[start] =0;
visited[start] = true;
for(int j=0; j<graph.get(start).size(); j++) {
d[graph.get(start).get(j).getIndex()] = graph.get(start).get(j).getDistance();
}
for(int i=0; i<n-1; i++) {
int now = getSmallestNode();
visited[now] = true;
for(int j=0; j<graph.get(now).size(); j++) {
int cost = d[now] +graph.get(now).get(j).getDistance();
if(cost <d[graph.get(now).get(j).getIndex()]) {
d[graph.get(now).get(j).getIndex()] = cost;
}
}
}
}
private static int getSmallestNode() {
int min = INF;
int index = 0;
for(int i=0; i<=n; i++) {
if(d[i]<min && !visited[i]) {
min = d[i];
index = i;
}
}
return index;
}
}
// 시간 복잡도: O(V^2), V는 노드 개수
/*
<입력>
6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2
<출력>
0
2
3
1
2
4
*/
SQL
복사
→ 최소 비용의 거리로 업데이트 시키려고 노드 개수 만큼 돌리고 젤 작은 수를 찾기 위해 노드 개수만큼 for문 실행한다.
→ 시간 복잡도: O(V^2)
다익스트라 알고리즘 구현 - 개선된 방법
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
class Node1 {
private int index;
private int distance;
public Node1(int index, int distance) {
this.index = index;
this.distance = distance;
}
public int getIndex() {
return this.index;
}
public int getDistance() {
return this.distance;
}
}
public class 다익스트라우선순위큐 {
private static final int INF = (int) 1e9;
private static int n,m,start;
private static ArrayList<ArrayList<Node1>> graph = new ArrayList<ArrayList<Node1>>();
private static PriorityQueue<Node1> queue = new PriorityQueue<Node1>((Node1 o1, Node1 o2) -> o1.getDistance()-o2.getDistance());
private static int[] d = new int[100001];
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<Node1>());
}
for(int i=0; i<m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
graph.get(a).add(new Node1(b,c));
}
Arrays.fill(d, INF);
dijkstra(start);
// 모든 노드로 가기 위한 최단 거리를 출력
for (int i = 1; i <= n; i++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (d[i] == INF) {
System.out.println("INFINITY");
}
// 도달할 수 있는 경우 거리를 출력
else {
System.out.println(d[i]);
}
}
}
private static void dijkstra(int start) {
d[start] = 0;
queue.offer(new Node1(start,0));
while (!queue.isEmpty()) {
Node1 node = queue.poll();
int dst = node.getDistance();
int now = node.getIndex();
if(d[now] < dst) continue;
for(int i =0; i<graph.get(now).size(); i++) {
int cost = d[now] + graph.get(now).get(i).getDistance();
if(d[graph.get(now).get(i).getIndex()] > cost) {
d[graph.get(now).get(i).getIndex()] = cost;
queue.offer(new Node1(graph.get(now).get(i).getIndex(), cost));
}
}
}
}
}
SQL
복사
→ 우선 순위 큐를 사용한다.
→ 우선 순위 큐에서 가장 작은 수 poll하는데 logV만큼 들고
→ while문과 for문은 간선의 개수만큼 돌린다고 볼 수 있다
→ 시간 복잡도: ElogV
플로이드 워셜 알고리즘
•
모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 상황
•
구현 과정은 다익스트라보다 짧지만 핵심 아이디어를 이해하는 것이 중요
•
매 단계마다 방문하지 않은 노드중에 최단 거리를 가지는 노드를 찾는 과정이 필요하지 않음
•
2차원 테이블에 최단 거리 정보를 저장 (인접 행렬)
•
다이나믹 프로그래밍 유형에 속함
→ 각 단계마다 특정한 노드 K를 거쳐가는 경우를 확인
D12 = min(D12, D1K + DK2)
→ 시간 복잡도 O(N^3)
→ 노드의 크기가 작을 경우에 사용
