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

1. 그래프(Graph)

그래프는 도로망이나 지하철뿐만 아니라 사회조직이나 인간관계, 데이터 및 네트워크 구성, 분자와 생물 유전자 등과 같은 현실의 복잡한 작업을 구조화하여 시각적으로 표현한 자료를 말한다. 특히, 선형 구조나 트리 구조로 표현하기 어려운 다대다 관계의 현상이나 사물 등을 가시적으로 설명할 때 유용하게 활용할 수 있는 도구이다.
그래프는 현상이나 사물을 정점의 모음과 이 정점의 사이를 잇는 간선의 모음으로 표현했다고 할 수 있으며, 두 정점이 간선으로 연결되어 있을 경우 인접이라고 한다. 이러한 특성으로 인해 주요 요소 간의 거리나 관계, 비용 등의 주제를 표현하거나 설계할 때 유용하다
2. 최단 경로 문제
(1) 특징
최단 경로 문제는 그래프상에 나타난 두 정점의 사이를 연결할 수 있는 경로 중에서 가장 짧은 경로를 찾는 과정이다. 여기서 짧다는 의미는 물리적인 거리뿐만 아니라 시간 혹은 비용과 관련한 거리 등과 같은 다양한 기준이 적용될 수 있다. 즉, 시간이나 비용 등의 요소는 가중치로 작용하며, 그래프상에서 음수로 주어지는 경우가 존재하게 된다. 따라서 그래프를 통한 최단 경로를 찾는 문제는 가중치…(생략)