다익스트라
-
[Algorithm] - 다익스트라Algorithm/Algorithm 2022. 8. 31. 00:51
다익스트라 방향, 무방향 그래프에서 하나의 시작점으로 부터 다른 Node까지의 최단 거리를 구하는 알고리즘 Edge에 음수인 가중치가 있다면 절대 사용 불가! 유사 알고리즘으로 A* 알고리즘이 존재하지만, 길찾기와 같이 Node가 엄청 많을 때 유사값을 찾는 용도이다. 거리가 확정되지 않은 Edge 중에서 가장 가까운 Edge를 선택한다는 그리디 알고리즘으로 부터 착안한다. O(V^2+E) => 갱신 가능 아래와 같은 그래프에서 1부터 시작한다면, 각 Node별로 최단 거리 값이 결과가 나타난다. 1에서는 갈 수 있는 Node가 2,3,4 총 3가지다. 이중에서 가장 작은 Edge는 Node 3과 연결된 2로 갱신 시키고 Node에 대해 확정을 시켜준다. 연결된 가장 작은 Edge는 Node 2와 연결된..
-
[BOJ] 1753번 - 최단경로Algorithm/BOJ 2022. 8. 31. 00:51
문제 BOJ 1753번 최단 경로 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 문제 이해 더보기 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까..