재원블로그 재원블로그

가중치가 있는 그래프에서 최단 경로를 찾는 알고리즘에는 대표적으로 다익스트라, 벨만-포드, 플로이드-워셜이 있다. 그 중 다익스트라에 대해서 정리하는 글이다. 다익스트라 알고리즘은 우선순위 큐를 이용할 경우 O(E + VlogV)로 알려져 있다. 여기서 E는 간선의 개수이고, V는 정점의 개수이다. 이 알고리즘은 무향, 유향 상관없이 적용 가능하지만, 음의 가중치가 있으면 사용할 수 없다. 다익스트라 알고리즘은 하나의 시작 정점에서 다른 정점들과의 최단 시간을 알아낼 때, 즉 1 : N일 때 사용할 수 있다. 다익스트라 알고리즘을 C++로 구현한 코드는 다음과 같다. #define INF 1000000000 int v; vector edges; vector dijkstra(int start) { vect..