모든 쌍 최단경로 문제1 [알고리즘] ep7) 최단경로 ㅁ최단경로 문제(shortest path problem): 가중그래프 두 개의 정점 u와 v가 주어졌을 때, u와 v 사이의 무게의 합이 최소인 경로를 구하는 문제최단경로길이: 간선들의 무게 합 응용: 인터넷 패킷 라우팅, 항공편 예약, 자동차 네비게이션 [최단경로 속성 2가지]속성1)최단경로의 부분경로(subpath) 역시 최단경로이다 속성2)출발정점으로부터 다른 모든 정점에 이르는 최단경로들의 트리가 존재한다 - 단일점 최단경로(single-source shortest path) - 최단경로는 무방향뿐만 아니라 방향그래프에서도 정의가 가능하다- 그래프에 음의 무게를 가진 싸이클이 있거나, 무방향그래프에 음의 무게를 가진 간선이 있으면 부정한다- 최단경로트리(shortest path tree)는 루트.. 2024. 7. 26. 이전 1 다음
