그래프에서의 최단 경로란?
최단 경로 정의
간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로
하나의 시작 정점에서 끝 정점까지의 최단 경로를 찾는 알고리즘
- 다익스트라(Dijkstra) 알고리즘
- 음의 가중치를 허용하지 않음- 벨만-포드(Bellman-Ford) 알고리즘)
- 음의 가중치 허용
모든 정점들에 대한 최단 경로 알고리즘
- 플로이드-워샬(Floyd-Warshall) 알고리즘
오늘은 다익스트라 알고리즘에 대해 배워보자
다익스트라 알고리즘 (Dijkstra Algorithm)
최단경로 알고리즘
한 정점에서 다른 모든 정점까지의 최단경로를 찾는 알고리즘
- 시작정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
- 시작 정점에서의 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다.
- 탐욕 기법을 사용한 알고리즘으로, MST의 프림 알고리즘과 유사하다.
프림 알고리즘 은 지난 게시물에서 공부했다.
원리
- 출발 노드 설정
- 최단 거리 테이블 초기화
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
- 위 과정에서 3번과 4번을 반복한다.
최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징 (최단 거리 테이블)
방법1. 간단한 다익스트라 알고리즘
시간 복잡도 :
V : 노드의 개수
- 각 노드에 대한 최단 거리를 담는 1차원 리스트 선언
- 단계마다 "방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인(순차 탐색)한다.
=> 최단 경로 문제에서 전체 노드 개수가 5000개 이하라면 이 방법으로 해결 가능.
=> 하지만 노드의 개수가 10,000개를 넘어가면 '개선된 다익스트라 알고리즘'을 이용해야한다.
수도 코드 (Pseudo Code)
s : 시작 정점, A : 인접 행렬, D : 시작정점에서의 거리 v : 정점 집합, U : 선택된 정점 집합 Dijkstra(s, A, D) U = {s}; FOR 모든 정점 v D[v] <- A[s][v] while U != V D[w] 가 최소인 정점 w ∈ V-U 를 선택 U <- U ∪ {w] FOR w에 인접한 모든 미방문 정점 v D[v] <- min(D[v], D[w] + A[w][v])
시뮬레이션 그림도 그려주고 싶은데
난 바쁘고 이해했으니까
생략하겠습니다.
Java Code
import java.io.*;
import java.util.*;
// 인접리스트 활용
public class Main
{
static class Node {
int vertex, weight;
Node next;
public Node(int vertex, int weight, Node next) {
this.vertex = vertex;
this.weight = weight;
this.next = next;
}
}
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine().trim());
int V = Integer.parseInt(st.nextToken()); // 정점 갯수
int E = Integer.parseInt(st.nextToken()); // 간선 갯수
st = new StringTokenizer(br.readLine().trim());
int start = Integer.parseInt(st.nextToken()); // 시작점 인덱스
int end = Integer.parseInt(st.nextToken()); // 도착점 인덱스
final int INF = Integer.MAX_VALUE;
Node[] adjList = new Node[V];
int[] minDinstance = new int[V];
boolean[] visited = new boolean[V];
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine().trim());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
adjList[from] = new Node(to, weight, adjList[from]);
} // 인접리스트 생성
Arrays.fill(minDinstance, INF);
minDinstance[start] = 0; // 출발지에서 출발지로의 비용 0으로 초기화
int min = 0, stopOver = 0;
for (int i=0; i<V; i++) { // 모든 정점이 다 처리될때까지 반복
// step1 : 미방문 정점 중 출발지에서 가장 가까운 정점 선택
min = INF;
stopOver = -1;
for (int j=0; j<V; j++) {
if (!visited[j] && min > minDinstance[j]) {
min = minDinstance[j];
stopOver = j;
}
}
if (stopOver == -1) break;
visited[stopOver] = true;
// if (stopOver == end) break; // 도착점이면 끝내기
// step2 : 미방문 정점들에 대해 선택된 경유지를 거쳐서 가는 비용과 기존 최소비용을 비교해서 업데이트
for (Node temp = adjList[stopOver]; temp != null; temp = temp.next) {
if (//!visited[temp.vertex]) &&
minDinstance[temp.vertex] > min + temp.weight) {
minDinstance[temp.vertex] = min + temp.weight;
}
}
}
System.out.println(minDinstance[end] != -1 ? minDinstance[end] : -1);
}
}
입력
6 11 0 5 0 1 3 0 2 5 1 2 2 1 3 6 2 1 1 2 3 4 2 4 6 3 4 2 3 5 3 4 0 3 4 5 6
출력
12
PQ를 이용한 다익스트라 코드
import java.io.*;
import java.util.*;
public class Main
{
static int V, E;
static int K; // 시작 정점
static List<List<Edge>> adjList = new ArrayList<>();
static int[] cost; // 시작 정점으로부터의 최소비용 관리
static boolean[] visit; // 꺼낼 때
static PriorityQueue<Edge> pq = new PriorityQueue<>((e1, e2) -> e1.c - e2.c);
static StringBuilder sb = new StringBuilder();
static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
K = Integer.parseInt(br.readLine());
visit = new boolean[V+1]; // 0 dummy
cost = new int[V+1];
// cost, adjList 초기화
for (int i=0; i<=V; i++) {
adjList.add(new ArrayList<Edge>());
cost[i] = INF;
}
for (int i=0; i<E; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
adjList.get(u).add(new Edge(v,w));
}
// 풀이
dijkstra();
for (int i=1; i<=V; i++) {
sb.append(cost[i] == INF ? "INF" : cost[i]).append("\n");
}
System.out.println(sb);
}
static void dijkstra() {
// 시작 정점 K
cost[K] = 0;
pq.offer(new Edge(K,0));
while (!pq.isEmpty()) {
Edge pe = pq.poll();
if (pe.c > cost[pe.v]) continue; // 가지치기
if (visit[pe.v]) continue; // 방문 pass
visit[pe.v] = true; // 방문 처리
for (Edge ne : adjList.get(pe.v)) {
if (ne.c + cost[pe.v] < cost[ne.v]) {
cost[ne.v] = ne.c + cost[pe.v];
pq.offer(new Edge(ne.v, cost[ne.v]));
}
}
}
}
static class Edge {
int v, c;
public Edge(int v, int c) {
this.v = v;
this.c = c;
}
}
}백준 - 최단경로
위 문제에 넣어보면 정답으로 나온다
PQ를 사용한 버전이 더 가독성이 좋고 간단하다
풀이
import java.io.*;
import java.util.*;
public class Main
{
static class Edge {
int v, c;
public Edge(int v, int c) {
this.v = v;
this.c = c;
}
}
static int N, E;
static int v1, v2; // 반드시 지나야 하는 두 정점
static List<List<Edge>> adjList = new ArrayList<>();
static int[] cost1, costV1, costV2;
static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // 정점갯수
E = Integer.parseInt(st.nextToken()); // 간선갯수
cost1 = new int[N+1];
costV1 = new int[N+1];
costV2 = new int[N+1];
for (int n=0; n<=N; n++) {
adjList.add(new ArrayList<Edge>());
}
for (int e=0; e<E; e++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
adjList.get(from).add(new Edge(to, weight));
adjList.get(to).add(new Edge(from, weight));
}
st = new StringTokenizer(br.readLine());
v1 = Integer.parseInt(st.nextToken());
v2 = Integer.parseInt(st.nextToken());
dijkstra(1, cost1);
dijkstra(v1, costV1);
dijkstra(v2, costV2);
if (cost1[N] == INF) System.out.println(-1);
else {
int path1 = cost1[v1] + costV1[v2] + costV2[N];
int path2 = cost1[v2] + costV2[v1] + costV1[N];
System.out.println(Math.min(path1, path2));
}
}
public static void dijkstra(int from, int[] cost) {
Arrays.fill(cost, INF);
PriorityQueue<Edge> pq = new PriorityQueue<>((o1,o2) -> (o1.c-o2.c));
pq.offer(new Edge(from,0)); // 시작점 입력
cost[from] = 0;
while (!pq.isEmpty()) {
Edge pe = pq.poll();
if (pe.c > cost[pe.v]) continue; // 가지치기 : 현재 꺼낸 노드가 이미 최소 비용이 아니라면 스킵
for (Edge ne : adjList.get(pe.v)) {
if (ne.c + cost[pe.v] < cost[ne.v]) {
cost[ne.v] = ne.c + cost[pe.v];
pq.add(new Edge(ne.v, cost[ne.v]));
}
}
}
}
}재밌는 문제였다
visited 를 다음의 가지치기로 생략할 수 있다.
if (pe.c > cost[pe.v]) continue; // 가지치기 : 현재 꺼낸 노드가 이미 최소 비용이 아니라면 스킵
TO DO
다음에는 모든 정점간의 최단거리를 구하는 플로이드-워셜을 공부해보자
자두과자