티스토리 뷰
다익스트라 알고리즘에 대해 자세히 설명된 곳을 추천한다.
http://www.playsw.or.kr/repo/cast/105
우선 위 주소로 가서 다익스트라 알고리즘이 어떻게 동작하는지 한번 살펴보길 추천한다. 단계별로 설명되어 있기 때문이 차근 차근 읽어보면 쉽게 이해할 수 있다.
내가 이해한 다익스트라 알고리즘은 출발지로부터 갈 수 있는 노드의 최단 거리를 모든 노드를 방문할 때까지 계속 갱하는 방법이다.
1. 먼저, 집에서 갈 수 있는 곳을 그림의 표에서 거리 칸에 써 넣는다.
2. 그리고 집에서 갈 수 있는 곳은 미용실, 슈퍼마켓, 영어학원 중에서 최단거리인 미용실로 간다.
3.다시 미용실에서 갈 수 있는 곳은 슈퍼마켓, 은행이다.(집은 이미 방문했으니 패스~)
여기서 슈퍼마켓으로 가는 경로는 집에서 바로 슈퍼마켓으로 가는 경로보다 짧다.
쉽게 말하면, 집->미용실->슈퍼마켓의 거리는 5+3=8인데 집->슈퍼마켓은 거리가 10이다.
그러니 그림의 표의 슈퍼마켓이 10에서 8로 값을 갱신하는 것이다.
이 부분이 다익스트라 알고리즘의 핵심인 것 같다. 알고리즘이 진행되면서 출발지인 집에서 갈 수 있는 노드들의 최단거리를 계속 갱신하는 것이다.
모든 곳을 다 방문하면 알고리즘은 종료된다.
알고리즘의 의사코드는 나무위키에서 퍼왔다.
function Dijkstra(Graph, Source): dist[source] ← 0 // 소스와 소스 사이의 거리 초기화 --출발지와 출발지의 거리는 당연히 0-- prev[source] ← undefined // 출발지 이전의 최적 경로 추적은 없으므로 Undefined create vertex set Q //노드들의 집합 Q(방문되지 않은 노드들의 집합) 생성 시작 for each vertex v in Graph: // Graph안에 있는 모든 노드들의 초기화 if v ≠ source: // V 노드가 출발지가 아닐 경우(출발지를 제외한 모든 노드!) dist[v] ← INFINITY // 소스와 V노드 사이에 알려지지 않은 거리 --얼마나 먼지 모르니까-- = 무한값 ( 모든 노드들을 초기화하는 값) prev[v] ← UNDEFINED // V노드의 최적경로 추적 초기화 add v to Q // Graph에 존재하고 방금 전 초기화된 V 노드를 Q(방문되지 않은 노드들의 집합)에 추가 //요약하자면, Graph에 존재하는 모든 노드들을 초기화한 뒤, Q에 추가함. while Q is not empty: // Q 집합이 공집합 아닐 경우, 루프 안으로! u ← vertex in Q with min dist[u] // 첫번째 반복에서는 dist[source]=0이 선택됨. 즉, u=source에서 시작 remove u from Q // U 노드를 방문한 것이므로 Q집합에서 제거 for each neighbor v of u: // U의 이웃노드들과의 거리 측정 alt ← dist[u] + length(u, v) // 출발지 노드 부터 계산된 U노드까지의 거리 + V에서 U의 이웃노드까지의 거리 //= source to U + V to U = source to U if alt < dist[v]: // 방금 V노드까지 계산한 거리(alt)가 이전에 V노드까지 계산된 거리(dist[v])보다 빠른 또는 가까운 경우 dist[v] ← alt // V에 기록된 소스부터 V까지의 최단거리를 방금 V노드까지 계산한 거리로 바꿈 prev[v] ← u // 제일 가까운 노드는 지금 방문하고 있는 노드(U)로 바꿈 return dist[], prev[] //계산된 거리값과 목적지를 리턴
그리고 응용1도 없이 다익스트라 알고리즘을 푸는 문제이다. 출처는 백준에서 퍼왔다.
https://www.acmicpc.net/problem/1916
코드는 나무위키의 의사코드를 참고해서 C언어로 만들었다. 그래프를 인접행렬로 표현했다. 노드의 개수가 많아지면, STL의 vector를 이용하는게 편할 것 같다.
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 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | #include <stdio.h> #define MAXNODE 1000 #define INFINIT 100000001 /* n : 노드의 개수, m : 버스 노선의 수 source : 출발지, destination : 목적지 adj[][] : 인접행렬 dist[] : 출발지로부터의 최소 비용 */ int n, m, source, destination; int adj[MAXNODE + 1][MAXNODE + 1]; long long dist[MAXNODE + 1]; void input() { int from, to, w; scanf ( "%d" , &n); scanf ( "%d" , &m); // 인접행렬을 모두 무한대 거리로 만든다. for ( int i = 1; i <= n; i++) for ( int j = 1; j <= n; j++) adj[i][j] = INFINIT; for ( int i = 0; i < m; i++) { scanf ( "%d %d %d" , &from, &to, &w); // ** A->B로 가는 버스가 여러대일 수 있다. if (adj[from][to] > w || adj[from][to] == 0) adj[from][to] = w; } scanf ( "%d %d" , &source, &destination); } void dikstra() { // Q : 방문지, 의사코드와 동일 int Q[MAXNODE + 1], Q_Size = n; for ( int v = 1; v <= n; v++) { dist[v] = INFINIT; Q[v] = 0;; } dist[source] = 0; while (Q_Size != 0) { int min_dst = INFINIT, u; long long alt; for ( int v = 1; v <= n; v++) { if (Q[v] == 0 && dist[v] < min_dst) { min_dst = dist[v]; u = v; } } Q[u] = 1; Q_Size--; for ( int v = 1; v <= n; v++) { if (adj[u][v] == INFINIT) continue ; alt = dist[u] + adj[u][v]; if (alt < dist[v]) dist[v] = alt; } } } int main() { input(); dikstra(); printf ( "%lld\n" , dist[destination]); return 0; } |
'알고리즘 > 다익스트라 최단거리' 카테고리의 다른 글
백준_플로이드 (0) | 2016.09.22 |
---|---|
백준_케빈 베이컨의 6단계 법칙 (0) | 2016.07.08 |
백준_파티 (0) | 2016.07.02 |