[최단거리] 다익스트라 알고리즘 (Dijkstra)
다익스트라 알고리즘이란?다익스트라 알고리즘은 기본적으로 greedy와 dp를 사용한 알고리즘으로 그래프의 최단 경로를 구하는 알고리즘이다. 하나의 정점에서 출발하는 최단 거리를 구하는 것이다. 이때 간선의 가중치는 양수여야 한다. 인접 행렬로 표현된 그래프의 경우 시간 복잡도 O(n^2)이지만 우선순위 큐를 사용하면 시간 복잡도 O(mlog n)까지 낮출 수 있다. 음의 가중치를 가지면 안되는 이유 다음과 같은 경우에 다익스트라 알고리즘은 A->B->D 총 비용 22가 가장 최소 경로라고 생각 할 것이다. (A-B-DB->C->D가 총-90 으로 값이 더 작다. 즉, 위와 같이 음의 가중치가 포함된 그래프의 최단 경로는 다익스트라 알고리즘으로 구할 수 없는 경우가 있다. 동작 과정출발지에서 인접한 노..
