Chapter 13. 경로 탐색: 다익스트라(Dijkstra) 알고리즘과 최단 경로 Chapter 13. 경로 탐색: 다익스트라(Dijkstra) 알고리즘과 최단 경로 13.1최단 경로 문제의 정의와 분류 체계 13.2단일 출발점 최단 경로와 전체 쌍 최단 경로의 구분 13.3그래프 가중치의 수학적 표현과 비용 함수 정의 13.4다익스트라 알고리즘의 기본 원리와 탐욕적 선택 전략 13.5다익스트라 알고리즘의 의사 코드와 알고리즘 명세 13.6완화(Relaxation) 연산의 정의와 최적 부분 구조 증명 13.7우선순위 큐를 이용한 다익스트라 알고리즘 구현 13.8이진 힙 기반 우선순위 큐의 시간 복잡도 분석 13.9피보나치 힙 기반 다익스트라 알고리즘의 최적 복잡도 13.10인접 리스트 표현에서의 다익스트라 알고리즘 동작 13.11인접 행렬 표현에서의 다익스트라 알고리즘 동작 13.12다익스트라 알고리즘의 정확성 증명 과정 13.13다익스트라 알고리즘의 시간 복잡도 상세 분석 13.14다익스트라 알고리즘의 공간 복잡도 분석 13.15음의 가중치 간선에서의 알고리즘 실패 원인 분석 13.16최단 경로 트리의 구성과 경로 역추적 기법 13.17다익스트라 알고리즘과 너비 우선 탐색의 관계 13.18다익스트라 알고리즘과 벨만-포드(Bellman-Ford) 알고리즘의 비교 13.19균일 비용 탐색(Uniform-Cost Search)과의 동치성 분석 13.20희소 그래프와 밀집 그래프에서의 성능 비교 13.21다중 목적지 최단 경로 탐색 전략 13.22동적 가중치 환경에서의 다익스트라 알고리즘 확장 13.23교통 네트워크에서의 최단 경로 탐색 응용 13.24통신 네트워크 라우팅에서의 다익스트라 알고리즘 적용 13.25지리 정보 시스템(GIS)에서의 경로 계획 활용 13.26다익스트라 알고리즘의 한계와 A* 탐색으로의 확장