Algorithm

[Algorithm] Dijkstra - 다익스트라

목표 최소비용 경로문제로 대표되는 Dijkstra 알고리즘에 대해 이해하고 학습한다. Dijkstra 알고리즘을 활용할 수 있는 알고리즘 문제를 풀어보고 정형화된 템플릿을 만들어보자. Dijkstra란 Dijkstra Dijkstra란 V개의 정점과 각각의 가중치(W)를 가진 E개의 간선을 가진 그래프에서 i번 정점에서 j번 정점까지로의 최소 가중치를 가지는, 최단 경로를 찾는 알고리즘이다. 아래는 Dijkstra 알고리즘을 활용할 수 있는 그래프의 예시이다. Dijkstra 알고리즘을 활용하기 위해서는 앞서 설명한 그래프, 정점 별 최소 가중치를 저장하기 위한 1차원 배열, 그래프 탐색을 위한 자료구조가 필요하다. 그래프 탐색을 위한 자료구조는 인접행렬과 우선순위 큐를 사용할 수 있고, 인접행렬을 개선..