[자료구조] [C＋＋]그래프에서 최단경로구하기

1. 그래프 이론 개요

그래프는 노드(정점)와 이들 간의 연결을 나타내는 간선(에지)으로 구성된 자료구조이다. 그래프는 현실 세계의 다양한 문제들을 수학적 구조로 모델링하는데 유용하며, 특히 네트워크, 지도, 소셜 미디어 분석 등 광범위하게 활용된다. 그래프는 크게 방향성 그래프와 무방향성 그래프로 구분되며, 각각의 특성에 따라 다양한 알고리즘이 적용된다. 예를 들어, 도로망은 무방향 그래프로 모델링할 수 있으며, 도시내의 교통 흐름을 분석하는 데 사용된다. 그래프의 종류로는 인접 행렬과 인접 리스트가 있는데, 인접 행렬은 정점의 수가 N일 때 O(N^2)의 공간 복잡도를 가지며, 밀집 그래프에 적합하다. 반면, 인접 리스트는 희소 그래프에 적합하며, 평균적으로 O(V + E)의 시간 복잡도를 갖는다. 최단경로 문제는 그래프 내에서 두 정점 사이의 가장 짧은 경로를 찾는 문제로, 네트워크 최적화, 물류 경로 설계, 통신망 설계 등에 필수적으로 활용된다. 특히, 미국 내 전국 버스 노선망에서는 약 15만 개 이상의 노선이 존재하며, 이 중 최단경로 알고리즘을 통해 승객 이동 시간을 평균 20% 이상 단축하는 사례가 보고되고 있다. 대표적인 최단경…