DAG最短路徑

Question

給定有向無環圖G = (V,E)和兩個不同的頂點s和t。邊和頂點都被賦予了實值權重。路徑的權重定義爲路徑上所有邊和頂點的總和。問題是要找到從s到t的最短加權簡單路徑。 （a）設計一個動態規劃算法並簡要描述它。 （b）設計一個貪婪算法並簡要描述它。 （c）儘可能提供一個算法的上限和下限。

我該怎麼做？ Dijkstra能用嗎？

Answer 1

我認爲可以使用Dijkstra的貪婪算法。我不知道其他人，對不起，夥計。