728x90
1. 다익스트라 알고리즘
- 그래프에서 출발 노드와 모든 노드 간의 최단 거리를 구하는 알고리즘이다.
- 시간 복잡도는 O(에지 수 * log 노드 수)이다.
2. 다익스트라 과정
- 인접 리스트로 그래프 구현
- 최단 거리 배열을 만들고 출발 노드는 0, 그 외 노드는 무한으로 초기화
- 최단 거리 배열에서 값이 가장 작은 노드 선택
- 선택한 노드에 연결된 노드의 값을 Min(선택 노드 최단 거리 값 + 에지 가중치, 연결 노드 최단 거리 값)으로 업데이트
- 모든 노드가 선택될 때까지 과정 3, 4를 반복
3. 예제 문제
[1753] 최단경로 (JAVA)
# 문제 설명 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점
spicyrisotto.tistory.com
[1916] 최소비용 구하기 (JAVA)
# 문제 설명 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A
spicyrisotto.tistory.com
[1446] 지름길 (JAVA)
# 문제 설명 매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고
spicyrisotto.tistory.com
728x90
'책 > Do it! 알고리즘 코딩 테스트 자바 편' 카테고리의 다른 글
| Day-16 위상 정렬 (0) | 2024.04.12 |
|---|---|
| Day-15 유니온 파인드 (0) | 2024.04.10 |
| Day-14 그래프의 표현 (0) | 2024.04.10 |
| Day-12 오일러 피 (0) | 2024.04.07 |
| Day-13 확장 유클리드 호제법 (0) | 2024.04.06 |
