📍 정의 및 특징
가중치가 있는 그래프에서 출발 노드에서부터 모든 노드 간 최단 거리 탐색 알고리즘
특정 지점까지의 거리 = A까지의 거리 + A에서 특정 지점까지 소요되는 거리
- 제약조건 : 엣지, 항상 양수여야 한다.
- 시간 복잡도 : O(E log V)
(모든 지점 간 최단 거리 구하는 시간 복잡도 : O(V³))
+ 인접 리스트 쓰는 게 더 효율적
+ 꼭 우선순위 큐를 사용해야 함. (사용자 정의 정렬)
+ 가중치 있는 그래프 담기 위한 노드 클래스 별도 구현 필요 (또는 int[])
#가중치O #양수 #모든정점간최단경로탐색
📍 필요 변수 · 자료구조
1. 인접 리스트
2. 최단 거리 배열
3. 우선순위 큐
4. 방문 배열
5. 노드 클래스
📍 실행 과정
- 인접 리스트로 그래프 구현 ⇨ (노드, 가중치) 형태
- 최단 거리 배열 D 초기화 ⇨ 출발 노드 : 0 / 이외 노드 : INF
- 최단 거리 배열에서 방문X & 최소값(=0) 가진 노드 선택
- 최단 거리 배열 업데이트
4-1)Min(선택 노드의 최단 거리 배열의 값 + 엣지 가중치, 연결 노드의 최단 거리 배열의 값)
(예: D[1] + 8 < D[2] = 0 + 8 < ∞ ⇒ D[2]값을 8로 갱신)
4-2) 업데이트 수행 시, 연결 노드를 우선순위 큐에 삽입 - 모든 노드가 선택될 때까지 과정 반복 ⇨ 방문 배열 visited 만들어 중복 처리
➕ 예제
[백준/JAVA] 1753번: 최단경로
🔺 문제 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정
bono039.tistory.com
[백준/JAVA] 1916번: 최소비용 구하기
🔺 문제 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정
bono039.tistory.com
[백준/JAVA] 18352번: 특정 거리의 도시 찾기
🔺 문제 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째
bono039.tistory.com
[백준/JAVA] 1504번: 특정한 최단 경로
📖 문제 https://www.acmicpc.net/problem/1504 💡 풀이 방식• 다익스트라필요 자료구조- 인접 배열 리스트- 시작점에서 각 정점까지 가는 최단 거리 저장용 int형 배열- N개의 각 정점에 대한 boolean
bono039.tistory.com
(참고)
Do it 알고리즘 코딩 테스트 자바편
'코테 > 알고리즘' 카테고리의 다른 글
| 벨만-포드 (0) | 2023.06.26 |
|---|---|
| 최단 경로 탐색 알고리즘 (0) | 2023.06.23 |
| 위상 정렬 (0) | 2023.06.23 |
| 시간 복잡도 면에서 좋은 정렬 방법 (0) | 2023.06.14 |
| DP (0) | 2023.05.29 |
