通過所有其他節點（NP-Hard？）從節點A到B的最短路徑

Question

我的問題：找到從節點A到節點B的最短路徑，該節點通過未加權的直接圖形的所有其他節點。我知道存在這樣一條路。

我相信這是NP-Hard，但我無法解釋它。我的教授喜歡讓算法在O(|V| + |E|)的運行時間上執行，其中V是一組節點和E邊緣集合。

看起來它與this problem類似，但Graph的屬性不同，它有什麼區別嗎？

Answer 1

是的，它是NP-hard。如果你的求解器在P中運行，那麼通過在每對點上運行它，你將有一個P時間求解器Hamiltonian Path。

answer you linked給出了更嚴格的證明。