-3
방향성 비순환 그래프 G = (V,E)과 두 개의 고유 정점 s 및 t이 주어졌습니다. 모서리와 정점 모두 실수 가중치가 할당됩니다. 경로의 가중치는 경로의 모든 모서리와 정점의 합으로 정의됩니다. 문제는 s에서 t으로 최단 가중치가 단순 경로를 찾는 것입니다.DAG 최단 경로
(a) 동적 프로그래밍 알고리즘을 디자인하고 간단하게 설명하십시오.
(b) 탐욕적인 알고리즘을 디자인하고 간단히 설명하십시오.
(c) 알고리즘 중 하나의 상한 및 하한을 최대한 줄입니다.
어떻게하면됩니까? Dijkstra를 사용할 수 있습니까?
이것은 숙제 문제처럼 들리지만 ... 문제를 해결하기 위해 무엇을 했습니까? 그리고 어디서 붙어 있습니까? –