알고리즘_그래프에서 한 정점에서 목적지까지 가는 여러 경로 중 최단 경로를 구하는 여러 가지 방법에 대해 생각해 보고 이를 정리하시오.

목차

1. 그래프(Graph)

2. 최단 경로 문제
1) 특징
2) 내비게이션 알고리즘

3. 다양한 최단 경로 문제 적용

4. 정리 및 느낀 점

5. 참고문헌

본문내용

1. 그래프(Graph)
그래프는 도로망이나 지하철뿐만 아니라 사회조직이나 인간관계, 데이터 및 네트워크 구성, 분자와 생물 유전자 등과 같은 현실의 복잡한 작업을 구조화하여 시각적으로 표현한 자료를 말한다. 특히, 선형 구조나 트리 구조로 표현하기 어려운 다대다 관계의 현상이나 사물 등을 가시적으로 설명할 때 유용하게 활용할 수 있는 도구이다.
그래프는 현상이나 사물을 정점의 모음과 이 정점의 사이를 잇는 간선의 모음으로 표현했다고 할 수 있으며, 두 정점이 간선으로 연결되어 있을 경우 인접이라고 한다. 이러한 특성으로 인해 주요 요소 간의 거리나 관계, 비용 등의 주제를 표현하거나 설계할 때 유용하다.

2. 최단 경로 문제
(1) 특징
최단 경로 문제는 그래프상에 나타난 두 정점의 사이를 연결할 수 있는 경로 중에서 가장 짧은 경로를 찾는 과정이다. 여기서 짧다는 의미는 물리적인 거리뿐만 아니라 시간 혹은 비용과 관련한 거리 등과 같은 다양한 기준이 적용될 수 있다. 즉, 시간이나 비용 등의 요소는 가중치로 작용하며, 그래프상에서 음수로 주어지는 경우가 존재하게 된다. 따라서 그래프를 통한 최단 경로를 찾는 문제는 가중치가 없는 그래프에서 가장 짧은 경로를 찾는 경우와 시간이나 비용 등과 같은 가중치가 존재하는 그래프에서 간선 사이 가중치의 합이 최소가 되는 경로를 찾는 문제로 나눌 수 있다.

참고 자료

김대일 외(2020), 「화재발생 시 대피시뮬레이션 시스템을 통한 최적대피경로 적용에 관한 연구」, 한국재난정보학회논문집 16(1), 96-110.
이용후 외(2014), 「내비게이션 경로설정에서 최단거리경로 탐색을 위한 A*와 Dijkstra 알고리즘의 하이브리드 검색법」, 전자공학회논문지 51(10), pp.109-117.
안성진(2015), 「최단 경로 알고리즘 - 빠른길 어떻게 찾는 것일까?」, 네이버 지식백과, 2015. 03. 27.
(terms.naver.com/entry.naver?docId=3579335&cid=59086&categoryId=59093)