16강. 다익스트라 알고리즘

[ 목차 ]

1. 가중 경로

2. 다익스트라 알고리즘

3. 수행시간 분석

 

1. 가중 경로 

1) 경로에 속하는 모든 간선의 값을 더한 값

 

2. 다익스트라 알고리즘

1) 하나의 시작점에서 하나의 도착점을 가는 최단경로를 찾는 알고리즘

2) 정점을 하나씩 추가하며 완화를 통해 새로운 경로에서 경로값을 계산하여 새로운 경로를 추가하여 최단 경로를 탐색

3) 간선이 음의 값을 가지면 불가능

ㅍ

 

3. 수행시간 분석