https://www.acmicpc.net/problem/1753    # 문제방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 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 이하의 자연수..

이번 게시글은 탐욕 알고리즘의 마지막 알고리즘으로 다익스트라 알고리즘을 정리할 예정이다. 목차는 다음과 같다. Dijkstra's algorithm (다익스트라 알고리즘) 탐욕알고리즘은 아래 게시글에 설명되어있다. https://wanna-developer02.tistory.com/51 [알고리즘] CHAP 4. The Greedy Approach (탐욕알고리즘) - Prim's alg (프림알고리즘) 이번 챕터에서는 탐욕알고리즘과 이를 이용하는 프림, 크루스칼, 다익스트라 알고리즘을 정리해보려고 한다. 한 게시물에 정리하기에는 내용이 너무 많아서 나눠서 정리할 예정이다. 목차는 다 wanna-developer02.tistory.com 1. Dijkstra 알고리즘 다익스트라 알고리즘은 가중치그래프에서 ..