統一成本搜索與深度優先搜索

Question

是否有任何一個統一成本搜索（dijkstra算法）返回比使用深度優先搜索更高成本的路徑的實例？

Answer 1

對於非負邊緣加權圖，Dijkstra算法將始終找到最短路徑。所以在非負加權圖中是不可能的。但是，在負邊加權圖中，Dijkstra不保證最短路徑，它可能會返回比DFS更高的成本路徑。

Answer 2

我不這麼認爲。迪克斯特拉應該返回最短路徑。