익명 사용자
로그인하지 않음
토론
기여
계정 만들기
로그인
IT 위키
검색
최단 경로 알고리즘
편집하기
IT 위키
이름공간
문서
토론
더 보기
더 보기
문서 행위
읽기
편집
원본 편집
역사
경고:
로그인하지 않았습니다. 편집을 하면 IP 주소가 공개되게 됩니다.
로그인
하거나
계정을 생성하면
편집자가 사용자 이름으로 기록되고, 다른 장점도 있습니다.
스팸 방지 검사입니다. 이것을 입력하지
마세요
!
최단 경로 알고리즘(Shortest path algorithm, 最短經路算法)은 그래프 상에서 한 정점에서 다른 정점으로의 최단 경로를 계산하기 위한 알고리즘들을 통칭하는 개념이다. ==개요== 최단 경로 알고리즘은 컴퓨터 과학, 수학, 물류, 네트워크 등 다양한 분야에서 핵심적인 알고리즘으로 사용된다. 그래프는 정점(vertex)과 간선(edge)으로 이루어지며, 각 간선에는 비용 또는 거리 등의 가중치가 할당된다. 이 알고리즘들은 이러한 가중치를 고려하여 특정 정점 간의 최소 비용 경로를 효율적으로 계산한다. 문제 유형은 다음과 같이 구분된다. *단일 시작점에서 모든 정점까지의 최단 경로 (Single-source shortest path) *모든 정점 쌍 사이의 최단 경로 (All-pairs shortest path) *특정 두 정점 사이의 최단 경로 (Single-pair shortest path) 수학적으로 그래프 G = (V, E)가 주어졌을 때, 각 간선 (u, v) ∈ E에는 가중치 w(u, v)가 정의된다. 정점 s에서 정점 t로 가는 경로 P = (s = v0, v1, ..., vk = t)가 있을 때, 경로 P의 총 가중치는 다음과 같이 정의된다. w(P) = w(v0, v1) + w(v1, v2) + ... + w(vk-1, vk) 최단 경로 알고리즘은 이 w(P)를 최소화하는 경로 P를 찾는다. ==주요 알고리즘== 대표적인 최단 경로 알고리즘은 다음과 같다. *[[다익스트라 알고리즘]]: 음의 가중치가 없는 그래프에서 단일 시작점 문제 해결. 시간 복잡도는 O((V+E)logV) *[[벨만-포드 알고리즘]]: 음의 가중치가 있는 경우에도 동작 가능. 시간 복잡도는 O(VE) *[[플로이드-워셜 알고리즘]]: 모든 정점 쌍 간 최단 경로 계산. 시간 복잡도는 O(V^3) *[[A* 알고리즘]]: 휴리스틱 기반 탐색 알고리즘. 실시간 경로 탐색에 효과적 ==예시== 다음 그래프에서 정점 A에서 C까지의 최단 경로를 계산한다. 그래프: A --(3)--> B --(1)--> C \ ^ \(5)--------------/ 가능한 경로: *A → B → C: 거리 3 + 1 = 4 *A → C: 거리 5 최단 경로는 A → B → C이며, 총 거리는 4이다. 수학적으로: *w(A → B → C) = w(A, B) + w(B, C) = 3 + 1 = 4 *w(A → C) = 5 min{w(A → B → C), w(A → C)} = min{4, 5} = 4 ==응용== 최단 경로 알고리즘은 다음과 같은 분야에 사용된다. *내비게이션 및 지도 서비스에서 경로 최적화 *통신 네트워크에서 패킷 전달 경로 계산 *게임에서 캐릭터의 경로 탐색 *공급망 및 물류의 경로 최적화 ==한계== *음의 사이클이 존재할 경우 일부 알고리즘은 정상 동작하지 않음 *실시간 환경에서는 계산 지연 문제가 발생할 수 있음 *대규모 그래프에서는 계산량이 많아 성능 최적화가 필요함 ==같이 보기== *[[그래프 이론]] *[[다익스트라 알고리즘]] *[[벨만-포드 알고리즘]] *[[플로이드-워셜 알고리즘]] *[[A* 알고리즘]] ==참고 문헌== *Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). *Introduction to Algorithms* (3rd ed.). MIT Press. ==각주== [[분류:알고리즘]] [[분류:그래프 이론]]
요약:
IT 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 라이선스로 배포된다는 점을 유의해 주세요(자세한 내용에 대해서는
IT 위키:저작권
문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요.
또한, 직접 작성했거나 퍼블릭 도메인과 같은 자유 문서에서 가져왔다는 것을 보증해야 합니다.
저작권이 있는 내용을 허가 없이 저장하지 마세요!
취소
편집 도움말
(새 창에서 열림)
둘러보기
둘러보기
대문
최근 바뀜
광고
위키 도구
위키 도구
특수 문서 목록
문서 도구
문서 도구
사용자 문서 도구
더 보기
여기를 가리키는 문서
가리키는 글의 최근 바뀜
문서 정보
문서 기록