PinguiOS

안녕하세요! Ick입니다. 오늘은 가중치가 음수가 아닌 그래프에서 하나의 노드로부터 다른 노드들까지의 최단거리를 알 수 있는 다익스트라 알고리즘에 대해 알아보려고합니다. 다익스트라 알고리즘을 그냥 있는 그대로 나타내는 방법과 우선순위 큐를 사용하는 방법이 있는데요... 저는 우선순위 큐를 사용한 다익스트라 알고리즘을 이해하는데 정말 오래 걸렸습니다.ㅠ,ㅠ 그래서 다신 까먹지 않기 위해 글을 써보려고 합니다! 다익스트라 알고리즘 - Dijkstra 우선 다익스트라 알고리즘은 간선의 음수인 가중치가 없는 그래프에서만 사용할 수 있습니다. 여기서 방향 그래프, 무방향 그래프는 상관이 없습니다. 또한 하나의 노드에서 다른 모든 노드의 최단거리를 구하는 알고리즘이란 것을 기억해야 합니다!! 위의 그래프로 다익스트..

문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 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개의 줄..