반응형

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

한 정점에서 다른 정점으로 가는 최단거리를 구하는 알고리즘으로 가중치가 음수면 사용이 불가능하다.

다익스트라는 최단거리는 최단거리들로 이루어져 있다는 Greedy한 아이디어로 만들어진 알고리즘이다.

주로 우선순위 큐와 BFS를 이용하여 구현되며, 작동 방식은 다음과 같다.

1. 아직 방문하지 않은 정점들 중 거리가 가장 짧은 정점을 하나 선택해 방문한다.

2. 해당 정점에서 인접하고 아직 방문하지 않은 정점들의 거리를 갱신한다.


* 작동 예시


0번 정점에서 시작한다고 가정하고, 위와 같은 그래프가 있을 때 작동방식은 다음과 같다.

 작동 방식

 방문한 정점

PrioirityQueue 

 사용가능한 간선

 1. 0번 정점에서 가까운 간선 중 최소 가중치를 가진 0-1 간선을 선택한다.

 0

 [7, 9, 14]

 0-1, 0-2, 0-3

 2. 0번 정점과 1번 정점에서 가중치가 작은 간선을 선택한다. 

(단, 1번정점에서 선택하는 경우는 0-1 간선의 가중치인 7을 더해야 한다.)

 1

 [9,  14, 10+7, 15+7]

 0-2, 0-5, 0-1-2, 0-1-3

 3. 0,1,2 정점에서 사이클을 만들지 않는 간선 중 가중치가 작은 간선을 선택한다.

 2

 [9+2, 14, 9+11, 7+15]

 0-2-5, 0-5, 0-2-3, 0-1-3

 4. 0,1,2,5 정점에서 사이클을 만들지 않는 간선 중 가중치가 작은 간선을 선택한다.

 5

 [9+11, 9+2+9, 7+15]

 0-2-3, 0-2-5-4, 0-1-3

 5. 0,1,2,3,5 정점에서 사이클을 만들지 않는 간선 중 가중치가 작은 간선을 선택한다.

 3

 [9+2+9, 9+11,6]

 0-2-5-4, 0-2-3-4

 6. 0,1,2,3,5 정점에서 사이클을 만들지 않는 간선 중 가중치가 작은 간선을 선택한다.

 4

 

 

위 순서를 통해 정점과 정점사이의 최단 거리를 구한다.

핵심은 최단거리는 최단거리들로 이루어져 있다는 생각이고, 선택한 정점과 인접한 최소한의 가중치를 가진 간선을 선택하는 것은 프림 알고리즘과 비슷하다.

하지만, 프림 알고리즘과 달리 우선순위 큐에 해당 가중치를 계속 더해가며 최단 경로를 찾는 알고리즘이다.

백준/1753 :: 최단경로 문제

백준/1753 :: 최단경로 풀이

반응형
저작자표시 비영리 변경금지

'∙Algorithm Tech' 카테고리의 다른 글

[Algorithm Tech]공통 부분 문자열과 최장 공통 부분 수열  (0) 2019.01.30
[Algorithm Tech] Segment Tree(세그먼트 트리)  (0) 2019.01.22
[Algorithm Tech] 최단 경로 알고리즘  (0) 2019.01.16
[Algorithm Tech] 최소 신장 트리(MST, Minimum Spanning Tree)  (0) 2019.01.16
반응형

* 핵심

우선순위큐를 이용하여 다익스트라를 구현

* 문제

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

* 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(stk.nextToken());
        int E = Integer.parseInt(stk.nextToken());
        int start = Integer.parseInt(br.readLine());
 
        ArrayList<Edge>[] edge = new ArrayList[V + 1];
        for (int i = 1; i <= V; i++) edge[i] = new ArrayList<>();
        int[] dijkstra = new int[V + 1];
        Arrays.fill(dijkstra, -1);
 
        for (int i = 0; i < E; i++) {
            stk = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(stk.nextToken());
            int v = Integer.parseInt(stk.nextToken());
            int w = Integer.parseInt(stk.nextToken());
            edge[u].add(new Edge(u, v, w));
        }
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[V + 1];
        pq.add(new Edge(0, start, 0));
        while (!pq.isEmpty()) {
            Edge e = pq.poll();
            if (!visited[e.v]) {
                visited[e.v] = true;
                dijkstra[e.v] = e.w;
                for (int i = 0; i < edge[e.v].size(); i++) {
                    pq.add(new Edge(e.v, edge[e.v].get(i).v, e.w + edge[e.v].get(i).w));    //해당 간선과 연결된 간선 
                }
            }
        }
 
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= V; i++) {
            int tmp = dijkstra[i];
            if (tmp != -1) sb.append(tmp + "\n");
            else sb.append("INF\n");
        }
        System.out.print(sb);
    }
 
 
    public static class Edge implements Comparable<Edge> {
        int u, v, w;
 
        Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
 
        @Override
        public int compareTo(Edge o) {
            return w - o.w;     //오름차순 정렬
        }
    }
}
 
cs


반응형
저작자표시 비영리 변경금지

'∙Algorithm' 카테고리의 다른 글

[Algorithm] 백준/1275 :: 커피숍2  (0) 2019.01.22
[Algorithm] 백준/2042 :: 구간 합 구하기  (0) 2019.01.22
[Algorithm] 백준/1922 :: 네트워크 연결  (0) 2019.01.16
[Algorithm] 백준/11055 :: 가장 큰 증가 부분 수열  (0) 2019.01.14
반응형

* 최단 경로 알고리즘

최소 신장 트리와 달리, 최단 경로 알고리즘은 출발 정점과 도착 정점이 존재한다.

즉, 최소 신장 트리처럼 모든 정점을 방문할 필요 없이 출발 정점에서 도착 정점까지 최단 경로만 찾으면 된다.


* 다익스트라 알고리즘    =>O(|E||log|V|)

다익스트라 알고리즘은 음의 가중치가 없을 때 우선순위 큐를 활용해 최단 경로를 구하는 알고리즘이다.

1. 출발 지점에서 시작하는 간선들 중 최소 가중치를 가지는 간선을 선택한다.

2. 해당 정점을 방문하면 해당 정점까지 필요한 가중치 + 해당 정점에서 방문할 수 있는 간선의 가중치 들을 우선순위 큐에 넣는다.

3. 위 과정을 목표 정점에 도착할 때까지 반복한다.

단, 음의 가중치가 존재해서는 안된다. => 벨만-포드 알고리즘 사용


* 벨만 - 포드 알고리즘    =>O(VE)



* 플로이드 와샬 알고리즘    =>O(n^3)

모든 경우의 수를 시도해보는 알고리즘이다.

2차원 배열 d의 초기값을 모두 무한대로 설정한다.

이후 해당 정점을 거쳐가는 최단거리가 있다면 해당 거리를 업데이트한다.

1
2
3
4
5
6
7
8
9
for (int k = 0; k < N; ++k) {            //거쳐가는 정점
    for (int i = 0; i < N; ++i) {        //시작 정점
        for (int j = 0; j < N; ++j) {    //도착 정점
            if (d[i][j] > d[i][k] + d[k][j]) {
                d[i][j] = d[i][k] + d[k][j];
            }
        }
    }
}
cs

즉, d[1][5] = d[1][k] + d[k][5]가 되는데 

d[1][1] + d[1][5]  or  d[1][2] + d[2][5]  or  d[1][3] + d[3][5]  or  d[1][4] + d[4][5]  or  d[1][5] + d[5][5] 중 최소값을 찾는다.

반응형
저작자표시 비영리 변경금지

'∙Algorithm Tech' 카테고리의 다른 글

[Algorithm Tech]공통 부분 문자열과 최장 공통 부분 수열  (0) 2019.01.30
[Algorithm Tech] Segment Tree(세그먼트 트리)  (0) 2019.01.22
[Algorithm Tech] 최소 신장 트리(MST, Minimum Spanning Tree)  (0) 2019.01.16
[Algorithm Tech] Scanner vs BufferedReader  (0) 2019.01.10

티스토리툴바