[Data Structure] 최단경로 - Dijkstra Algorithm

최단경로 - 정점 i ~ 정점 j까지 간선들의 weight 합이 최소가 되는 경로 Dijkstra 하나의 시작 정점 ~ 모든 다른 정점까지의 최단 경로 Floyd 모든 정점 ~ 다른 모든 정점까지의 최단 경로 Dijkstra Algorithm - 탐욕적 방법 (greedy method) 이용 - 특정 시작 정점 ~ 다른 모든 정점까지의 최단 경로 계산 - 가중치가 음수가 아닐 때 정상적으로 작동 - Dijkstra → Greedy → DP(최단경로 + 길찾기) / 매 상황에서 가장 비용이 적은 최선의 정점 선택 - 시작정점으로부터 거리를 저장하는 distance[] 1차원 배열이 필요 - O(n²) 시작 정점(v) 선택 시작 정점으로부터 다른 모든 정점까지의 distance 업데이트 (한 번에 갈 수 없..

2021.12.25