최단 경로 (Shortest Path) 알고리즘 이란?
- 가장 짧은 경로를 찾는 알고리즘 (ex 길 찾기 문제)
- 문제를 그래프로 표현하고, 각 지점을 노드, 지점간 연결된 도로들은 간선이라 함.
- 최단 경로 알고리즘에는 그리디 알고리즘과 다이나믹 프로그래밍이 그대로 적용
1 : N (One-To-All)
한 지점에서 다른 모든 지점까지의 최단경로 구하기 (단일 시작점으로 부터 각 정점에 이르는 최단 경로)
- 다익스트라
- 음의 가중치를 허용하지 않는 최단 경로
- 벨만 포드 (Bellman Ford)
- 음의 가중치를 허용하는 최단 경로
N : N (All-To-All)
모든 지점에서 모든 지점까지의 최단경로 구하기 (모든 정점 쌍 사이의 최단경로를 모두 구하기)
- 플로이드 워셜 (Floyd Warshall)
다익스트라 알고리즘
그리디와 동적 계획법이 합쳐진 형태입니다.
그래프에서 특정 노드에서 출발하여 다른 모든 노드로 가는 각각의 최단 경로를 구해주는 알고리즘입니다.
단, 모든 링크의 가중치(길이)는 양의 정수 값이어야 합니다.
- 기능 : 출발 노드와 모든 노드 간의 최단 거리 탐색
- 특징 : 엣지는 모두 양수
- 시간 복잡도(노드 수:V, 에지 수: E) : O(ElogV)
특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어졌을 때 다익스트라 알고리즘을 사용하면 문제를 해결할 수 있습니다.
동작 방식
- 인접 리스트로 그래프 구현하기
- 인접 행렬도 가능하지만, 크기가 클 것을 대비해 인접 리스트로 구현하기
- 최단 거리 배열 초기화하기
- 출발 노드는 0, 이외의 노드는 무한대로 설정
- 값이 가장 작은 노드 고르기
- 최단 거리 배열 업데이트하기
- 선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값 업데이트
- 1단계에서 저장해 놓은 연결 리스트를 이용해 현재 선택된 노드의 엣지들을 탐색하고 업데이트
- 연결 노드의 최단 거리는 두 값 중 더 작은 값으로 업데이트
- Min(선택 노드의 최단 거리 배열의 값 + 엣지 가중치, 연결 노드의 최단 거리 배열의 값)
- 과정 3~4를 반복해 최단 거리 배열 완성하기
- 모든 노드가 처리될 때까지 과정 3~4를 반복
- 과정 4에서 선택 노드가 될 때마다 다시 선택하지 않도록 방문 배열을 만들어 처리
- 모든 노드가 선택될 때까지 반복하면 최단 거리 배열이 완성
다익스트라 알고리즘은 출발 노드와 그 외 노드간의 최단 거리를 구하는 알고리즘입니다.
엣지는 항상 양수여야 한다는 제약이 있습니다.
다익스트라는 출발 노드와 도착 노드간의 최단 거리를 구하는 알고리즘이 아니라,
출발 노드와 이외의 모든 노드 간의 최단 거리를 표현하는 알고리즘 입니다.
예시 문제
https://www.acmicpc.net/problem/1753
C++ 풀이
#include <stdio.h>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;
vector<pair<int,int> > node[20005];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;
int value[20005];
int main(){
int n,e,k;
int u,v,w;
scanf("%d %d",&n,&e);
scanf("%d",&k);
for(int i=0;i<e;i++){
scanf("%d %d %d",&u,&v,&w);
node[u].push_back(make_pair(v,w));
}
for(int i=1;i<=n;i++)
value[i] = INF;
value[k] = 0;
pq.push(make_pair(0,k));
while(!pq.empty()){
int x = pq.top().first;
int U = pq.top().second;
pq.pop();
for(int i=0;i<node[U].size();i++){
int V = node[U][i].first;
int W = node[U][i].second;
if(x+W<value[V]){
value[V] = x+W;
pq.push(make_pair(x+W,V));
}
}
}
for(int i=1;i<=n;i++)
if(value[i]==INF) printf("INF\n");
else printf("%d\n",value[i]);
return 0;
}Java 풀이
public class P1753_최단경로 {
public static int V, E, K;
public static int distance[];
public static boolean visited[];
public static ArrayList<Edge_1753> list[];
public static PriorityQueue<Edge_1753> q = new PriorityQueue<Edge_1753>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
K = Integer.parseInt(br.readLine());
distance = new int[V + 1];
visited = new boolean[V + 1];
list = new ArrayList[V + 1];
for (int i = 1; i <= V; i++) {
list[i] = new ArrayList<Edge_1753>();
}
for (int i = 0; i <= V; i++) {
distance[i] = Integer.MAX_VALUE;
}
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());
list[u].add(new Edge_1753(v, w));
}
q.add(new Edge_1753(K, 0)); // K를 시작점으로 설정
distance[K] = 0;
while (!q.isEmpty()) {
Edge_1753 current = q.poll();
int c_v = current.vertex;
if (visited[c_v]) {
continue; // 기 방문 노드는 다시 큐에 넣지 않습니다.
}
visited[c_v] = true;
for (int i = 0; i < list[c_v].size(); i++) {
Edge_1753 tmp = list[c_v].get(i);
int next = tmp.vertex;
int value = tmp.value;
if (distance[next] > distance[c_v] + value) { // 최소 거리로 업데이트
distance[next] = value + distance[c_v];
q.add(new Edge_1753(next, distance[next]));
}
}
}
for (int i = 1; i <= V; i++) { // 거리 배열 출력
if (visited[i]) {
System.out.println(distance[i]);
} else {
System.out.println("INF");
}
}
}
}
class Edge_1753 implements Comparable<Edge_1753> {
int vertex, value;
Edge_1753(int vertex, int value) {
this.vertex = vertex;
this.value = value;
}
public int compareTo(Edge_1753 e) {
if (this.value > e.value) {
return 1;
} else {
return -1;
}
}
}벨만 포드 알고리즘
- 기능 : 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색
- 특징 : 음수 가중치 엣지가 있어도 수행 가능, 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음
- 시간 복잡도(노드 수:V, 에지 수: E) : O(VE)
특징
- 음의 가중치를 가지는 간선도 가능하다.
- 음의 사이클의 존재 여부를 확인할 수 있다.
- 최단거리를 구하기 위해서 V-1번 E개의 모든 간선을 확인한다.
- 음의 사이클 존재 여부를 확인하기 위해서 한 번 더 E개의 간선을 확인한다.
- 총 연산횟수는 V*E이다. 따라서 시간복잡도는 O(VE)이다.
- V번째 모든 간선을 확인하였을 때 거리 배열이 갱신되었다면, 그래프 G는 음의 사이클을 가지는 그래프이다.
- 그래프 모든 엣지에 대해 edge relaxation을 시작노드를 제외한 전체 노드수 만큼 반복 수행한 뒤, 마지막으로 그래프 모든 엣지에 대해 edge relaxation을 1번 수행해 준다. 이때 한번이라도 업데이트가 일어난다면 음의 사이클이 존재한다는 뜻이 되어서 결과를 구할 수 없다는 의미의 false를 반환하고 함수를 종료한다.
이러한 문제점을 해결하기 위해 나온 알고리즘이 벨만 포드 입니다.
기본적으로 다익스트라와 동일하지만 핵심 차이점은 간선의 가중치가 음일 때도 최소 비용을 구할 수 있습니다.
다만 시간복잡도가 늘어나기 때문에 가중치가 모두 양수일 경우 다익스트라를 사용하는 것이 좋습니다.
시간 복잡도가 늘어나는 이유는 그리디하게 최소 비용 경로를 찾아가는 다익스트라와 달리, 벨만 포드는 모든 경우의 수를 고려하는 동적 계획법이 사용되기 때문입니다.
그렇다면 모든 경우의 수를 어떻게 고려할까?
그 방법은 매 단계 마다 모든 간선을 전부 확인하는 것입니다.
다익스트라는 출발 노드에서만 연결된 노드를 반복적으로 탐색하며 다른 모든 노드까지의 최소 거리를 구했습니다.
하지만 벨만 포드는 모든 노드가 한번씩 출발점이 되어 다른 노드까지의 최소 비용을 구합니다.
동작 방식
- 엣지 리스트로 그래프를 구현하고 최단 경로 배열 초기화하기
- 벨만 포드 알고리즘은 엣지를 중심으로 동작하므로 그래프를 엣지 리스트로 표현
- 최단 경로 배열은 출발 노드는 0, 나머지 노드는 무한대로 초기화
- 모든 엣지를 확인해 정답 배열 업데이트하기
- 최단 거리 배열에서 업데이트 반복 횟수는 노드 개수 -1 입니다.
- 노드 개수가 N이고, 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 엣지의 최대 개수는 N - 1 이기 때문입니다.
- 특정 엣지 E = (s,e,w) 에서 다음 조건을 만족하면 업데이트를 실행합니다.
D[s] != 무한대 이며 D[e] > D[s] + w 일 때 D[e] = D[s] + w로 배열 업데이트- 음수 사이클이 없을 때 N - 1번 엣지 사용 횟수를 반복하면 출발 노드와 모든 노드 간의 최단 거리를 알려주는 배열 완성
- 음수 사이클 유무 확인하기
- 음수 사이클 유무를 확인하기 위해 모든 엣지를 한번씩 다시 사용해 업데이트 되는 노드가 발생하는지 확인
- 만약 업데이트 되는 노드가 있다면 음수 사이클이 있다는 뜻 -> 2번에서 찾은 배열이 무의미하고 최단 거리를 찾을 수 없는 그래프라는 뜻
벨만 포드 알고리즘을 사용해 최단 거리를 구하는 문제보다 음수 사이클을 판별하는 문제가 더 빈번하게 출제됩니다. 따라서 마지막에 한 번 더 모든 엣지를 사용해 업데이트 되는 노드가 존재하는 지 확인해야 합니다.
예시 문제
https://www.acmicpc.net/problem/11657
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class P11657_타임머신 {
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int N, M;
static long distance[];
static Edge edges[];
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
edges = new Edge[M + 1];
distance = new long[N + 1];
Arrays.fill(distance, Integer.MAX_VALUE); // 최단거리 배열 초기화
for (int i = 0; i < M; i++) { // 간선 리스트에 데이터 저장하기
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int time = Integer.parseInt(st.nextToken());
edges[i] = new Edge(start, end, time);
}
// 벨만포드 알고리즘 수행
distance[1] = 0;
for (int i = 1; i < N; i++) { //N보다 하나 적은 수만큼 반복
for (int j = 0; j < M; j++) {
Edge edge = edges[j];
// 더 작은 최단거리 가 있는 경우 갱신
if (distance[edge.start] != Integer.MAX_VALUE
&& distance[edge.end] > distance[edge.start] + edge.time) {
distance[edge.end] = distance[edge.start] + edge.time;
}
}
}
boolean mCycle = false;
for (int i = 0; i < M; i++) { // 음수 cycle 확인
Edge edge = edges[i];
if (distance[edge.start] != Integer.MAX_VALUE
&& distance[edge.end] > distance[edge.start] + edge.time) {
mCycle = true;
}
}
if (!mCycle) { // 음의 cycle이 없는 경우
for (int i = 2; i <= N; i++) {
if (distance[i] == Integer.MAX_VALUE) {
System.out.println("-1");
} else {
System.out.println(distance[i]);
}
}
} else { // 음의 cycle이 있는 경우
System.out.println("-1");
}
}
}
class Edge { // 간선리스트를 편하게 다루기 위해 클래스로 별도 구현
int start, end, time; // 시작점, 도착점, 걸리는 시간
public Edge(int start, int end, int time) {
this.start = start;
this.end = end;
this.time = time;
}
}플로이드 워셜 알고리즘
- 기능 : 모든 노드간에 최단 경로 탐색
- 특징 : 음수 가중치 엣지가 있어도 수행 가능, 동적 계획법의 원리를 이용해 알고리즘에 접근
- 시간 복잡도(노드 수: V) : O(V^3)
플로이드 워셜 알고리즘은 모든 노드 간의 최단거리를 구할 수 있습니디.
플로이드 워셜 알고리즘은 그래프 상에서 음의 가중치가 있더라도 최단 경로를 구할 수 있습니다.
하지만 음의 가중치와 별개로 음의 사이클이 존재한다면 벨만 포드 알고리즘을 사용해야 합니다.
플로이드 워셜 알고리즘은 모든 노드 간의 최단거리를 구하고 이 때, 점화식이 사용되기에 동적 계획법에 해당합니다. 동적 계획법에 해당하므로 최단 거리를 업데이트할 테이블이 필요합니다.
이 때 모든 노드간의 최단 거리이므로 2차원 배열이 사용됩니다.
특정 한 노드에서 출발하는 다익스트라가 1차원 배열을 사용하는 것과 차이점이 있습니다.
가장 핵심적인 원리는 A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때, 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것 입니다.
즉, 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이루어진다는 의미입니다.
(즉, 정점 A와 정점 B 사이의 최단 경로는 A-B이거나 A-K-B 입니다. 만약 경유지(K)를 거친다면 최단 경로를 이루는 부분 경로 역시 최단 경로입니다. 다시 말해, 만약 A-B의 최단 경로가 A-K-B라면 A-K와 K-B도 각각 최단 경로입니다.)
다음과 같은 점화식을 도출할 수 있습니다.
D[S][E] = Min(D[S][E] , D[S][K] + D[K][E])
for k in range(1, V+1): # via
graph[k][k] = 0 # 사이클 없으므로 자기 자신 0
for i in range(1, V+1): # src
for j in range(1, V+1): # dst
graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])동작 방식
- 배열을 선언하고 초기화하기
- D[S][E] 는 노드 S에서 노드 E 까지의 최단 거리를 저장하는 배열이라 정의
- S와 E의 값이 같은 칸은 0, 다른 칸은 무한대로 초기화 (S == E 는 자기 자신에게 가는 데 걸리는 최단 경로 값)
- 최단 거리배열에 그래프 데이터 저장하기
- 출발 노드는 S, 도착 노드는 E, 이 엣지의 가중치는 W라고 했을 때 D[S][E] = W 로 엣지의 정보를 배열에 입력 -> 인접 행렬로 표현
- 점화식으로 배열 업데이트하기
- 점화식을 3중 for문의 형태로 반복함녀서 배열의 값 업데이트
예시 문제
https://www.acmicpc.net/problem/11404
import java.io.*;
import java.util.StringTokenizer;
public class P11404_플로이드 {
private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int N, M;
static int distance[][];
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
distance = new int[N + 1][N + 1];
for (int i = 1; i <= N; i++) { // 인접 행렬 초기화
for (int j = 1; j <= N; j++) {
if (i == j) {
distance[i][j] = 0;
} else {
distance[i][j] = 10000001; // 충분히 큰수로 저장
}
}
}
for (int i = 0; i < M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
if (distance[s][e] > v) {
distance[s][e] = v;
}
}
for (int k = 1; k <= N; k++) { // 플로이드 워셜 알고리즘 수행
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (distance[i][j] > distance[i][k] + distance[k][j]) {
distance[i][j] = distance[i][k] + distance[k][j];
}
}
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (distance[i][j] == 10000001) {
System.out.print("0 ");
} else {
System.out.print(distance[i][j] + " ");
}
}
System.out.println();
}
}
}
고생하셨습니당~~