1. 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제로, 가중치 그래프에서 간선의 가중치의 합이 최소가 되게 하는 경로를 찾는 것이 목적이다. 1) 단일 출발(single-source) 그래프 내 특정 노드에서 출발하여, 그래프 내 모든 다른 노드에 도착하는 가장 짧은 경로를 찾는 문제이다. 2) 단일 도착(single-destination) 모든 노드들로부터 출발하여, 그래프 내 특정 노드로 도착하는 가장 짧은 경로를 찾는 문제이다. 3) 단일 쌍(single-pair) 주어진 노드 u, v간 최단 경로를 찾는 문제이다. 4) 전체 쌍(all-pair) 그래프 내 모든 노드 쌍에 대한 최단 경로를 찾는 문제이다. 2. 최단 경로 알고리즘의 종류 다익스트라(Dijkstra) 벨만포드(bel..
[문제] 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 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 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다...
1. 다익스트라(Dijkstra)란 그래프에서 최단거리를 구하는 알고리즘이다. 모든 간 양수이어야 한다. 출발 노드와 도착 노드간의 최단거리를 구하는 것이 아니라 출발 노드와 나머지 노드간의 최단 거리를 표현하는 것. 2. 알고리즘 로직 다익스트라는 단일 출발 문제에 해당한다. 다익스트라 알고리즘은 BFS와 유사하다. 1) 주어진 데이터를 그래프로 구현하기 시간 복잡도를 고려하여 인접 행렬보다는 인접 리스트로 구현하는 것이 좋다. 인접 리스트에 연결된 배열은 (노드, 가중치)와 같은 형태로 구현을 한다. 2) 최단 거리 배열 초기화하기 최단 거리 배열을 생성하고, 출발 노드는 0, 나머지는 무한(99,999,999, "INF"라고 표현)으로 초기화한다. 우선 순위 큐에 출발 노드와 거리를 먼저 넣는다. ..
