다익스트라

다익스트라 알고리즘( 방향, 무방향 그래프에서 )
- 하나의 시작점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘
- 기능은 플로이드가 더 좋음.
- 플로이드는 음수인 간선이 있는건 상관이 없고 음수인 사이클이 있을때 문제발생.
- 다익스트라는 음수의 가중치를 가지는 간선이 있으면 아예 사용 불가.

풀이 방법

자기 자신과의 거리는 0이므로 1번 인덱스의 값은 0이다.
인접한 정점 중 가장 가까운, 가중치가 작은 정점을 최단 거리 테이블에 넣어 확정시킨다.

우선순위 큐를 이용한 다익스트라 알고리즘!

1. 우선순위 큐에 (0, 시작점)을 추가.
2. 우선순위 큐에서 거리가 가장 작은 원소를 선택, 해당 거리가 최단 거리 테이블에 있는 값과 다를 경우 넘어감.
3. 원소가 가리키는 정점을 v라고 할 때, v와 이웃한 정점들에 대해 최단 거리 테이블 값보다 v를 거쳐가는 것이 더 작은 값을 가질 경우 최단 거리 테이블의 값을 갱신하고 우선순위 큐에 (거리, 이웃한 정점의 번호)를 추가.
4. 우선순위 큐가 빌 때 까지 2, 3번 과정을 반복.