[자료구조] 다익스트라 알고리즘 (Dijkstra Algorithm)

최단 경로 알고리즘

: 정점 u와 정점 v를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로

- 간선이 없으면 가중치를 무한대로 처리

 

다익스트라 알고리즘

: 시작 정점 v에서 모든 다른 정점까지의 최단 경로 찾음

> 시작 정점 v : 최단경로탐색의 시작 정점

> 집합 S: 시작 정점 v로부터의 최단 경로가 이미 발견되 정점들의 집합

> dist배열 : S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단거리를 기록하는 배열

- 매 단계에서 최소 distance 인 정점을 S에 추가

- 새로운 정점이 S에 추가되면 dist 갱신