728x90
◇ 설명
◎ 최단 경로 문제
: 주어진 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로의 길이를 찾는 문제 ( 가중치가 있는 그래프 )
∎ 다익스트라( Dijkstra )
: 하나의 시작 정점에서 다른 모든 정점까지 최단 경로를 구하는 단일 시작점 최단 경로 문제.
- (n - 1) 개의 경로
- 음의 가중치를 허용하지 않음
∎ 벨만 포드( Bellman-ford )
: 하나의 시작 정점에서 다른 모든 정점까지 최단 경로를 구하는 단일 시작점 최단 경로 문제.
- (n - 1) 개의 경로
- 음의 가중치를 허용.
- 가중치 합이 음인 사이클은 절대 허용하지 않음.
- 간선을 최대 1개 사용하는 최단 경로, 최대 2개, ... 식으로 최대 n-1개 사용하는 최단 경로까지 구해나감
∎ 플로이드 워샬( Floyd-warshall )
: 모든 정점 쌍 간의 최단 경로를 구함 ( 모든 쌍 최단 경로 문제 ).
- n (n - 1) 개의 경로
- 동적 계획법을 이용
- 벨만-포드 알고리즘의 연장선상에 있는 방법
∎ 사이클이 없는 유향 그래프( DAG : Directed Acyclic Graph )의 최단 경로
: 하나의 시작 정점에서 다른 모든 정점까지 최단 경로를 구함
- (n - 1) 개의 경로
- DAG에서는 모든 정점을 한 줄로 늘어놓을 때, 뒤에 위치한 정점부터 앞에 위치한 정점으로 가는 간선은
존재하지 않도록 하는 정점들의 순열이 존재함 -> 위상 정렬
- 간선들의 가중치의 부호를 모두 바꾸어 수행하면 최장 경로를 구할 수 있음
◇ 코드
∎ 다익스트라( Dijkstra )
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
public class Graph_ShortestPath_dijkstra {
static class Path implements Comparable<Path> {
int v, d; // vertex num, distance from start vertex
Path( int v, int d ) {
this.v = v;
this.d = d;
}
@Override
public int compareTo( Path o ) {
return d - o.d;
}
}
static class Node {
int u, v, w; // vertex num, vertex_connected num, weight
Node( int u, int v, int w ) {
this.u = u;
this.v = v;
this.w = w;
}
}
// list
public static int[] dijkstra_list( int d[], List<List<Node>> e, int s, int n ) {
int i, u, v, d_u, w, d_v;
//boolean c[] = new boolean[n];
for( i = 0; i < n; i++ )
d[i] = Integer.MAX_VALUE;
d[s] = 0;
PriorityQueue<Path> pq = new PriorityQueue<>();
pq.add( new Path( s, 0 ) );
while( !pq.isEmpty() ) {
Path p = pq.remove();
u = p.v; d_u = p.d;
if( d[u] < d_u ) continue;
//if( c[u] ) continue;
//c[u] = true;
for( Node nd : e.get(u) ) {
v = nd.v; // connected vertex num
w = nd.w; // connected weight
d_v = d_u + w;
if( d[v] > d_v ) { // if( d[v] > d_v && !c[v] ) {
pq.add( new Path( v, d_v ) );
d[v] = d_v;
}
}
}
return d;
}
// array
public static int[] dijkstra_arr( int d[], int e[][], int s, int n ) { // distance, edge, start vertex, num of vertex
int i, u, v, d_u, w, d_v;
for( i = 0; i < n; i++ )
d[i] = Integer.MAX_VALUE;
d[s] = 0;
PriorityQueue<Path> pq = new PriorityQueue<>();
pq.add( new Path( s, 0 ) );
while( !pq.isEmpty() ) {
Path p = pq.remove();
u = p.v; d_u = p.d;
if( d[u] < d_u ) continue;
for( i = 0; i < n; i++ ) {
if( e[u][i] > 0 ) {
v = i; // connected vertex num
w = e[u][i]; // connected weight
d_v = d_u + w;
if( d[v] > d_v ) {
pq.add( new Path( v, d_v ) );
d[v] = d_v;
}
}
}
}
return d;
}
public static void main(String[] args) { /* 백준 1753번 문제 참고 */
int n = 5, s = 0, i; // vertex_num, vertex_start
int d[] = new int[n]; // vertex
// list
List<List<Node>> e_ls = new LinkedList<>(); // edge
for( i = 0; i < n; i++ )
e_ls.add( new LinkedList<Node>() );
e_ls.get( 4 ).add( new Node ( 4, 0, 1 ) );
e_ls.get( 0 ).add( new Node ( 0, 1, 2 ) );
e_ls.get( 0 ).add( new Node ( 0, 2, 3 ) );
e_ls.get( 1 ).add( new Node ( 1, 2, 4 ) );
e_ls.get( 1 ).add( new Node ( 1, 3, 5 ) );
e_ls.get( 2 ).add( new Node ( 2, 3, 6 ) );
// array
int e[][] = new int[n][n]; // edge
e[4][0] = e[4][0] > 0 ? Math.min( e[4][0], 1 ) : 1;
e[0][1] = e[0][1] > 0 ? Math.min( e[0][1], 2 ) : 2;
e[0][2] = e[0][2] > 0 ? Math.min( e[0][2], 3 ) : 3;
e[1][2] = e[1][2] > 0 ? Math.min( e[1][2], 4 ) : 4;
e[1][3] = e[1][3] > 0 ? Math.min( e[1][3], 5 ) : 5;
e[2][3] = e[2][3] > 0 ? Math.min( e[2][3], 6 ) : 6;
d = dijkstra_list( d, e_ls, s, n );
d = dijkstra_arr( d, e, s, n );
StringBuilder sb = new StringBuilder();
for( int a : d )
sb.append( ( a == Integer.MAX_VALUE ? "INF" : a ) + "\n" );
System.out.println( sb.toString() );
}
}
∎ 벨만 포드( Bellman-ford )
더보기
import java.util.ArrayList;
import java.util.List;
public class Graph_ShortestPath_bellmanFord {
static class Node {
int u, v, w; // vertex num, vertex_connected num, weight
Node( int u, int v, int w ) {
this.u = u;
this.v = v;
this.w = w;
}
}
static final int max = Integer.MAX_VALUE;
// list
public static long[] bellmanFord_list( long d[], List<List<Node>> e, int s, int n ) {
int i, k, u, v, w; long d_v;
for( i = 0; i < n; i++ )
d[i] = max;
d[s] = 0;
for( k = 0; k < n-1; k++ ) {
for( u = 0; u < n; u++ ) {
if( d[u] == max ) continue;
for( Node nd : e.get(u) ) {
v = nd.v;
w = nd.w;
d_v = d[u] + w;
if( d[v] > d_v )
d[v] = d_v;
}
}
}
for( u = 0; u < n; u++ ) {
if( d[u] == max ) continue;
for( Node nd : e.get(u) ) {
v = nd.v;
w = nd.w;
d_v = d[u] + w;
if( d[v] > d_v )
return new long[] {};
}
}
return d;
}
// array
public static long[] bellmanFord_arr( long d[], int e[][], int s, int n ) {
int i, k, u, v;
for( i = 0; i < n; i++ )
d[i] = max;
d[s] = 0;
for( k = 0; k < n-1; k++ ) {
for( u = 0; u < n; u++ ) {
if( d[u] == max ) continue;
for( v = 0; v < n; v++ ) {
if( e[u][v] == max ) continue;
if( d[v] > d[u] + e[u][v] )
d[v] = d[u] + e[u][v];
}
}
}
for( u = 0; u < n; u++ ) {
if( d[u] == max ) continue;
for( v = 0; v < n; v++ ) {
if( e[u][v] == max ) continue;
if( d[v] > d[u] + e[u][v] )
return new long[] {};
}
}
return d;
}
public static void main(String[] args) { /* 백준 11657번 문제 참고 */
int n = 3, s = 0, i; // vertex_num, vertex_start
long d[] = new long[n]; // vertex
// list
List<List<Node>> e_ls = new ArrayList<>(); // edge
for( i = 0; i < n; i++ )
e_ls.add( new ArrayList<Node>() );
e_ls.get( 0 ).add( new Node ( 0, 1, 4 ) );
e_ls.get( 0 ).add( new Node ( 0, 2, 3 ) );
e_ls.get( 1 ).add( new Node ( 1, 2, -1 ) );
e_ls.get( 2 ).add( new Node ( 2, 0, -2 ) );
// array
int e[][] = new int[n][n]; // edge
for( i = 0; i < n; i++ )
for( j = 0; j < n; j++ )
e[i][j] = max;
e[0][1] = e[0][1] != max ? Math.min( e[0][1], 4 ) : 4;
e[0][2] = e[0][2] != max ? Math.min( e[0][2], 3 ) : 3;
e[1][2] = e[1][2] != max ? Math.min( e[1][2], -1 ) : -1;
e[2][0] = e[2][0] != max ? Math.min( e[2][0], -2 ) : -2;
d = bellmanFord_list( d, e_ls, s, n );
d = bellmanFord_arr( d, e, s, n );
StringBuilder sb = new StringBuilder();
int len = d.length;
if( len == 0 )
sb.append(-1);
else {
for( i = 0; i < n; i++ )
sb.append( ( d[i] == max ? -1 : d[i] ) + "\n" );
}
System.out.print( sb.toString() );
}
}
∎ 플로이드 워샬( Floyd-warshall )
더보기
public class Graph_ShortestPath_floydWarshall_array {
public static int[][] floydWarshall( int d[][], int e[][], int n ) {
int i, j, k;
for( i = 0; i < n; i++ )
for( j = 0; j < n; j++ )
d[i][j] = e[i][j];
for( k = 0; k < n; k++ ) { // 중간 정점 집합
for( i = 0; i < n; i++ ) { // 시작 정점
for( j = 0; j < n; j++ ) { // 마지막 정점
if( i == j ) continue;
if( d[i][k] == 0 || d[k][j] == 0 ) continue;
if( d[i][j] == 0 || ( d[i][j] > d[i][k] + d[k][j] ) )
d[i][j] = d[i][k] + d[k][j];
}
}
}
return d;
}
public static void main(String[] args) { /* 백준 11404번 문제 참고 */
int n = 5, i, j; // vertex_num
int d[][] = new int[n][n]; // vertex ( distance )
int e[][] = new int[n][n]; // edge
e[0][1] = e[0][1] > 0 ? Math.min( e[0][1], 2 ) : 2;
e[0][2] = e[0][2] > 0 ? Math.min( e[0][2], 3 ) : 3;
e[0][3] = e[0][3] > 0 ? Math.min( e[0][3], 1 ) : 1;
e[0][4] = e[0][4] > 0 ? Math.min( e[0][4], 10 ) : 10;
e[1][3] = e[1][3] > 0 ? Math.min( e[1][3], 2 ) : 2;
e[2][3] = e[2][3] > 0 ? Math.min( e[2][3], 1 ) : 1;
e[2][4] = e[2][4] > 0 ? Math.min( e[2][4], 1 ) : 1;
e[3][4] = e[3][4] > 0 ? Math.min( e[3][4], 3 ) : 3;
e[2][4] = e[2][4] > 0 ? Math.min( e[2][4], 10 ) : 10;
e[2][0] = e[2][0] > 0 ? Math.min( e[2][0], 8 ) : 8;
e[0][3] = e[0][3] > 0 ? Math.min( e[0][3], 2 ) : 2;
e[4][0] = e[4][0] > 0 ? Math.min( e[4][0], 7 ) : 7;
e[2][3] = e[2][3] > 0 ? Math.min( e[2][3], 2 ) : 2;
e[4][1] = e[4][1] > 0 ? Math.min( e[4][1], 4 ) : 4;
d = floydWarshall( d, e, n );
StringBuilder sb = new StringBuilder();
for( i = 0; i < n; i++ ) {
for( j = 0; j < n; j++ )
sb.append( d[i][j] + "\t" );
sb.append("\n");
}
System.out.println( sb.toString() );
}
}
∎ 사이클이 없는 유향 그래프( DAG : Directed Acyclic Graph )의 최단 경로
더보기
import java.util.*;
public class Graph_ShortestPath_DAG_list { // 정점 번호는 [0, n)
static final int max = Integer.MAX_VALUE;
static class Node {
int u, v, w; // vertex num, vertex_connected num, weight
Node(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
}
public static int[] dag(int[] d, List<List<Node>> edge_out, int[] degree_in, int s, int n) {
int i, v, w;
for (i = 0; i < n; i++)
d[i] = max;
d[s] = 0;
int t[] = new int[n], idx = 0; // topologicalSort
PriorityQueue<Integer> top = new PriorityQueue<>();
for (i = 0; i < n; ++i)
if (degree_in[i] == 0)
top.add(i);
while (idx < n) {
int u = top.remove();
t[idx++] = u;
for (Node node : edge_out.get(u)) {
v = node.v;
degree_in[v]--;
if (degree_in[v] == 0)
top.add(v);
}
}
for (int u : t) {
for (Node node : edge_out.get(u)) {
v = node.v;
w = node.w;
if (d[u] == max) continue;
if (d[v] > d[u] + w)
d[v] = d[u] + w;
}
}
return d;
}
public static void main(String[] args) {
int n = 5, s = 0, i; // vertex_num, vertex_start
int d[] = new int[n]; // vertex
List<List<Node>> edge_out = new LinkedList<>(); // edge out
for (i = 0; i < n; i++)
edge_out.add(new LinkedList<Node>());
edge_out.get(4).add(new Node(4, 0, 1));
edge_out.get(0).add(new Node(0, 1, 2));
edge_out.get(0).add(new Node(0, 2, 3));
edge_out.get(0).add(new Node(0, 3, 5));
edge_out.get(2).add(new Node(2, 3, 6));
int[] degree_in = new int[n];
degree_in[0]++;
degree_in[1]++;
degree_in[2]++;
degree_in[3]++;
degree_in[3]++;
d = dag(d, edge_out, degree_in, s, n);
StringBuilder sb = new StringBuilder();
for (int a : d)
sb.append((a == max ? "INF" : a) + "\n");
System.out.println(sb.toString());
}
}
◇ 출처 : 쉽게 배우는 알고리즘 ( 문병로 )
반응형
'컴퓨터 공학 ( Computer Science ) > 알고리즘 ( Algorithm )' 카테고리의 다른 글
| [알고리즘] 트리 순회 ( Tree Traversal ) (0) | 2021.03.20 |
|---|---|
| [알고리즘] 최소 스패닝 트리 ( MST : Minimum Spanning Tree ) (0) | 2021.03.20 |
| [알고리즘] 그래프 탐색 ( Graph Search ) - 깊이 우선(DFS), 너비 우선(BFS ) (0) | 2021.03.20 |
| [알고리즘] 이분/이진 탐색 ( Binary Search ) (0) | 2021.03.20 |
| [알고리즘 기법] 분기한정법 ( Branch and Bound ) (0) | 2021.03.20 |