Page 9 -

ALGORITHM & DATA STRUCTURES

13.10 그래프 탐색 예(4): 트리 동적 계획법(*) 287
13.11 정리 291

13.12 연습 문제 292

14장 그래프(2): 최단 경로 문제 293

14.1 최단 경로 문제란? 294
14.1.1 가중치 유향 그래프 294
14.1.2 단일 시작점 최단 경로 문제 295
14.1.3 음의 변과 음의 닫힌 경로 295
14.2 최단 경로 문제 정리 296

14.3 완화 297
14.4 DAG의 최단 경로 문제: 동적 계획법 300

14.5 단일 시작점 최단 경로 문제: 벨만-포드 알고리즘 301
14.5.1 벨만-포드 알고리즘 아이디어 302
14.5.2 벨만-포드 알고리즘 구현 303
14.5.3 벨만-포드 알고리즘의 정확성(*) 305
14.6 단일 시작점 최단 경로 문제: 다익스트라 알고리즘 307
14.6.1 두 종류의 다익스트라 알고리즘 307
14.6.2 단순한 다익스트라 알고리즘 307
14.6.3 다익스트라 알고리즘의 직감적인 이미지 310
14.6.4 다익스트라 알고리즘 정확성(*) 312
14.6.5 희소 그래프인 경우: 힙을 사용한 고속화(*) 313
14.7 모든 쌍의 최단 경로 문제: 플로이드-워셜 알고리즘 317

14.8 참고: 포텐셜과 차분 제약계(*) 320
14.9 정리 321
14.10 연습 문제 321

025