![]()
1. 다익스트라(Dijkstra) 란? 다익스트라 알고리즘이란 하나의 그래프에서의 최단 경로 탐색 알고리즘이며, 우리가 흔히 알고있는 동적계획법 즉 다이나믹 프로그래밍을 활용한 최단경로 탐색 알고리즘이다. 한 정점에서 모든 정점까지의 최단거리를 구할 때 사용하며, 주어진 그래프중에서 음의 가중치가 없는 그래프에서 사용 가능하다. 음의 가중치가 있을 경우 벨만-포드 알고리즘을 사용하여 해결할 수 있다. 2. Default Logic 다익스트라 알고리즘 동작 반복 과정 1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. 2. 현재 위치한 정점을 거쳐 다른 노드로 넘어가는 가중치 값을 계산하여 최소 비용을 갱신한다. 3. 위의 과정을 목표한 노드에 도달 할 때까지 반복한다. 이해를 돕기 위해..
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. Logic - 기본 다익스트라 문제이다. 문제에서 나온대로 한 정점에서 모든 정점으로의 최단 경로를 구하는 다익스트라 알고리즘을 사용하면 풀 수 있다. 다 돌고 배열에서 값만 하나씩 출력해주면 되는 문제 2. Code #include using namespace std; const int INF = 10000000; // 시작 노드에서 해당 노드까지의 경..
https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1. Logic - 다익스트라는 한 정점에서 모든 정점으로 가는 최단경로를 구하는 알고리즘이다. 이 문제는 한 정점에서 모든 정점으로 가는 최단거리 + 다시 집에가는 최단거리 두개를 구해서 더해야 한다 2. Code #include using namespace std; const int INF = 987654321; //최소 비용 배열 int d[1001]; vect..
