알고리즘 Dijkstra 최단경로탐색

Dijkstra algorithm(다익스트라 알고르즘)

그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘

일반적인 형태로는 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단 경로를 찾는다. 

원래 알고리즘은 우선순위 큐를 사용하지 않았기 때문에 시간 복잡도 $$O(|V|^2)$$

우선적으로 구현해볼 것은 일반적인 형태이지만, 음의 간선을 포함할 수 없다.

사진에서 보이는 표 같은 경우는 "노드 1"을 기준 삼아서 연결되어 있는 꼭짓점과 연결을 확인한다.

이 다음 "노드"를 기준삼아서 기존에 값과 비교를 한 뒤에 최소값으로 표기를 하게 되면 된다.

이러한 방법은 모든 꼭짓점을 기준으로 할 때까지 반복이기에 위에서 말한 시간 복잡도를 갖게 된다.