경로 편집하기

'''경로'''(Path)는 그래프 이론에서 한 정점에서 다른 정점까지 이동할 수 있는 정점과 간선의 연속된 연결을 의미한다.  경로는 여러 분야에서 활용되며, 최단 경로 문제, 네트워크 라우팅, 교통 시스템 등에서 중요한 개념이다.
==정의==
*그래프 '''G = (V, E)'''에서 '''경로 P'''는 정점들의 시퀀스로 정의된다.
*수학적으로, 경로 P는 다음과 같이 표현된다.
**P = (v<sub>1</sub>, v<sub>2</sub>, ..., v<sub>k</sub>)
**모든 i에 대해 (v<sub>i</sub>, v<sub>i+1</sub>) ∈ E를 만족해야 한다.

*경로의 길이(length)는 사용된 '''간선의 개수'''를 의미하며, k개의 정점을 포함하는 경로의 길이는 '''k - 1'''이다.
*가중 그래프에서 경로 P의 '''가중치 W(P)'''는 경로를 구성하는 간선들의 가중치 합으로 정의된다.
**W(P) = ∑<sub>i=1</sub><sup>k-1</sup> w(v<sub>i</sub>, v<sub>i+1</sub>)
**여기서 w(v<sub>i</sub>, v<sub>i+1</sub>)는 간선 (v<sub>i</sub>, v<sub>i+1</sub>)의 가중치이다.
==경로의 종류==
*'''단순 경로(Simple Path)'''
**중복된 정점이 없는 경로
**P = (v<sub>1</sub>, v<sub>2</sub>, ..., v<sub>k</sub>), 단, v<sub>i</sub> ≠ v<sub>j</sub> (i ≠ j)

*'''사이클(Cycle)'''
**시작 정점과 끝 정점이 동일한 경로
**P = (v<sub>1</sub>, v<sub>2</sub>, ..., v<sub>k</sub>, v<sub>1</sub>)

*'''해밀턴 경로(Hamiltonian Path)'''
**모든 정점을 정확히 한 번씩 방문하는 경로
**|V(P)| = |V|

*'''오일러 경로(Eulerian Path)'''
**모든 간선을 정확히 한 번씩 지나는 경로
**|E(P)| = |E|
==최단 경로 알고리즘==
그래프에서 두 정점 간의 최단 거리를 찾는 주요 알고리즘은 다음과 같다.
*'''다익스트라 알고리즘 (Dijkstra's Algorithm)'''
**가중 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾음.
**시간 복잡도: O((V + E) log V)

*'''벨만-포드 알고리즘 (Bellman-Ford Algorithm)'''
**음수 가중치를 포함한 그래프에서도 최단 경로를 구할 수 있음.
**시간 복잡도: O(VE)

*'''플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)'''
**모든 정점 쌍 간의 최단 경로를 구하는 알고리즘.
**시간 복잡도: O(V³)

*'''A* 알고리즘 (A* Search Algorithm)'''
**휴리스틱을 사용하여 최단 경로를 탐색하는 방식.
**주어진 목표 정점까지의 예상 비용 f(v) = g(v) + h(v)를 사용.
==경로의 응용==
*'''네트워크 라우팅'''
**인터넷 및 통신 네트워크에서 최적의 패킷 전달 경로를 찾는 데 사용됨.

*'''내비게이션 시스템'''
**GPS 및 지도 애플리케이션에서 최단 거리 및 최적 경로 탐색.

*'''교통 시스템'''
**도로망 및 철도망에서 최적의 이동 경로를 설계하는 데 활용됨.

*'''생물정보학'''
**DNA 배열 정렬 및 유전자 네트워크 분석에 사용됨.
==같이 보기==
*[[그래프 이론]]
*[[최단 경로 알고리즘]]
*[[다익스트라 알고리즘]]
*[[벨만-포드 알고리즘]]
*[[플로이드-워셜 알고리즘]]
==참고 문헌==
*Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). ''Introduction to Algorithms''. MIT Press.
*[https://en.wikipedia.org/wiki/Path_(graph_theory) Wikipedia - Path (Graph Theory)]

*
[[분류:자료 구조]]
[[분류:알고리즘]]
설명	입력하는 내용	문서에 나오는 결과
기울임꼴	''기울인 글씨''	기울인 글씨
굵게	'''굵은 글씨'''	굵은 글씨
굵고 기울인 글씨	'''''굵고 기울인 글씨'''''	*굵고 기울인 글씨*