이 프로그램은 대학교 2학년 알고리즘 기말 프로젝트 때 개발한 것입니다. 팀 프로젝트 과제가 그래프 알고리즘 중 하나를 이용하여 기본 알고리즘 및 응용 프로그램 구현이었습니다. 팀 회의 끝에 '관광정보안내'라는 아이디어를 구상하였고 Dijkstra 알고리즘을 이용하여 구현을 하였습니다.
1. Dijkstra 알고리즘이란?
Dijkstra 알고리즘은 출발점과 도착점 사이의 최단 경로를 구하는 알고리즘으로 시간복잡도는 θ(n^2) 입니다.
다른 알고리즘과 비교해본다면 그래프의 모든 정점간의 최단거리를 구하는 Floyd 알고리즘을 들 수 있는데 시간복잡도를 통해 효율성을 비교해보면 Floyd 알고리즘의 시간복잡도는 θ(n^3) 이므로 Dijkstra 알고리즘이 뛰어나다는 것을 알 수 있습니다. 또한 관광정보안내 프로그램에서는 출발점과 도착점의 값이 입력이 되기 때문에 모든 정점간의 최단거리를 구하는 Floyd 알고리즘을 사용하는 것보다 Dijkstra 알고리즘을 이용하는 것이 사용성에 적합하다고 판단하였습니다.
2. Dijkstra 알고리즘의 응용
기본적인 Dijkstra 알고리즘의 시간복잡도는 θ(n^2) 이며 조금만 응용하면 시간복잡도를 줄일 수 있습니다.
Dijkstra 알고리즘을 링크드 리스트로 구현하고 Binary Heap 으로 구현된 우선순위 큐를 이용하여 구현하면 시간복잡도는 기존의 θ(n^2) 이 아닌 θ((m+n)logn)이 됩니다. 이 프로그램은 LinkedList + Binary Heap + Dijkstra 알고리즘을 혼합하여 구현되어 기존의 Dijkstra 알고리즘보다 효율성이 좋습니다.
3. Dijkstra 알고리즘에 대한 자세한 설명이 되어 있는 사이트
- 위키피디아 ( [링크] ← 이 링크를 클릭하시면 위키피디아의 Dijkstra 알고리즘 페이지로 연결됩니다.)
