Algorithm/최단거리

BOJ#1916 최소비용 구하기

밤이2209 2016. 11. 30. 14:48

BOJ#1916 최소비용 구하기


* 문제

https://www.acmicpc.net/problem/1916



* 풀이


다익스트라 알고리즘을 이용합니다.


* 다익스트라 알고리즘 (Dijkstra algorithm)


1. 개요

 : 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다. 


 : 다익스트라 알고리즘은 각각의 꼭짓점 v에 대해 s(시작점)에서 v까지의 최단 거리 d[v]를 저장하면서 작동한다. 알고리즘의 시작 시에 d[s]=0이고, s가 아닌 다른 모든 꼭짓점 v에 대해서는 d[v]=∞로 놓아 다른 꼭짓점에 대해서는 아직 최단 경로를 모른다는 사실을 표시한다. 알고리즘이 종료되었을 때 d[v]는 s에서 v까지의 최단 경로의 거리를 나타내게 되고, 만약 경로가 존재하지 않으면 거리는 여전히 무한대로 남는다.


 : 다익스트라 알고리즘은 변 경감(edge relaxation)이라고 불리는 기본 연산을 바탕으로 한다. s에서 u까지의 최단 경로(d[u])를 이미 알고 있고, u에서 v까지 길이가 w(u,v)인 변 (u, v)가 존재할 때, s에서 v까지의 최단 경로는 u까지의 최단 경로에 변 (u, v)를 추가함으로써 얻을 수 있다. 이 경로의 비용은 d[u]+w(u, v)가 되며, 이 비용이 현재의 d[v] 값보다 낮으면 d[v]를 새로운 값으로 바꾼다.



2. 실행 시간

 : 가장 간단한 구현으로, Q의 집합을 연결 리스트나 배열 구조로 구현하고 Extract-Min(Q) 함수를 단순한 선형 탐색으로 구현했을 때 실행 시간은 O(n^2)간이 된다.


만약 희소 그래프(sparse graph), 즉 n^2보다 훨씬 작은 개수의 변만을 갖는 그래프에 대해서는, 인접 리스트와 바이너리 힙 또는 피보나치 힙으로 구현한 우선순위 큐를 이용해 다익스트라 알고리즘을 더 효율적으로 구현할 수 있다. 이진 힙을 이용하면 실행 시간은 O((m+n)log n) 시간이 되고, 피보나치 힙을 통해 O((m+n)log n) 시간까지 개선할 수 있다.


3. 의사 코드


아래 알고리즘 의사코드에서 u := Extract_Min(Q)는 꼭짓점의 집합 Q에서 가장 작은 d[u]값을 찾은 다음 그 꼭짓점 u를 Q에서 제거한 후 반환하는 함수를 가리킨다.

 1   function Dijkstra(G, w, s)
 2      for each vertex v in V[G]                        // 초기화
 3            d[v] := infinity
 4            previous[v] := undefined
 5      d[s] := 0                                                     //덮어쓰기
 6      S := empty set
 7      Q := set of all vertices
 8      while Q is not an empty set                      // 알고리즘의 실행
 9            u := Extract_Min(Q)                                //집합 Q에서 d[u]가 최소인 u를 찾아 빼냄
10           S := S union {u}                                      //빼낸 u를 S에 삽입
11           for each v with edge (u,v) defined
12                  if d[v] > d[u] + w(u,v)
13                        d[v] := d[u] + w(u,v)              // 변(u,v)의 경감
14                        previous[v] := u                     //경로 추적할 때 쓰임//

만약 s에서 모든 v에 까지의 최소 경로를 찾는 것이 아니라, s에서 특정 꼭짓점 t까지의 최단 거리만을 알고 싶다면 8번째 행에 u != t의 조건을 추가하면 된다.


previous[]가 구해지면, 이를 이용해 다음과 같이 s에서 t까지의 최단 경로를 얻을 수 있다.

1 S := empty sequence
2 u := t
3 while defined u
4       insert u to the beginning of S
5       u := previous[u]

이제 S는 s에서 t까지의 최단 경로 위에 있는 꼭짓점들의 목록이 된다.


출처 :https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98



- 1916번 문제 주의점


버스 비용을 입력 받을 때

즉, 노드 → 노드로 가는 간선(weight)를 입력 받을 때

중복되어 입력될 수 있음.


예) 아래와 같이 입력이 될 수 있으므로 1 → 2 간선의 비용은 최소값인 3으로 유지해야함.

1 2 3

1 2 5

1 2 7



+ 추천하는 다익스트라 기본 문제

https://www.acmicpc.net/problem/13424




* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%231916_CalculateMinimumCost



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/*
* BOJ#1916 최소비용 구하기
* https://www.acmicpc.net/problem/1916
*/

public class Main {

static final int INF = 1000000000;

public static void main(String[] args) throws IOException {

int n;
int m;
int[][] w;
int[] d;
boolean[] visited;
int start, end;

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

n = Integer.parseInt(br.readLine());
m = Integer.parseInt(br.readLine());

w = new int[n + 1][n + 1];
d = new int[n + 1];
visited = new boolean[n + 1];

for (int i = 0; i < n + 1; i++) {

d[i] = INF;
visited[i] = false;
for (int j = 0; j < n + 1; j++) {
w[i][j] = INF;

}
}
for (int i = 0; i < m; i++) {

int a, b;
int weight;

StringTokenizer st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
weight = Integer.parseInt(st.nextToken());

//w[a][b] = weight;
if (w[a][b] > weight) {

w[a][b] = weight;
}
}

StringTokenizer st = new StringTokenizer(br.readLine());
start = Integer.parseInt(st.nextToken());
end = Integer.parseInt(st.nextToken());

dijkstra(start, n, m, w, d, visited);
System.out.println(d[end]);

}

static void dijkstra(int start, int n, int m, int[][] w, int[] d, boolean[] visited) {

int u;
int dist;

d[start] = 0;

for (int i = 1; i < n + 1; i++) {

dist = INF + 1;
u = -1;

for (int j = 1; j < n + 1; j++) {

if (!visited[j] && d[j] < dist) {

u = j;
dist = d[j];
}
}

for (int j = 1; j < n + 1; j++) {

if (d[j] > d[u] + w[u][j]) {

d[j] = d[u] + w[u][j];
}
}

visited[u] = true;
}
}
}








'Algorithm > 최단거리' 카테고리의 다른 글

BOJ#1261 알고스팟  (0) 2017.03.30
BOJ#1162 도로포장  (0) 2017.03.22
BOJ#1753 최단경로  (2) 2017.03.21
BOJ#1865 웜홀  (0) 2017.01.19
BOJ#11657 타임머신  (1) 2017.01.17