找到圖中所有頂點之間的最短路徑而不給出開始點或結束點

Question

我知道旅行商問題，但有沒有其他更適合我的需求/描述的算法/問題？我需要藉助這種數學描述來描述我的問題。

我有一組已知的啓動和端點的節點。所以我只需要計算最短的方式來訪問這兩者之間的所有三點。 Dijkstra和類似的算法試圖找到兩點之間的最短路徑，所以在這裏他們可能不會訪問所有點之間的所有點。還是有一種算法找到最短路線並訪問兩點之間的所有點？

Answer 1

您可以使用蟻羣優化算法來實現。請參閱Ant colony optimization algorithms。

Answer 2

您的問題的一般情況的複雜性至少與Traveling Salesman問題一樣高。想象一下你的兩個終點基本處於同一位置的情況，那麼你的問題就等同於旅行推銷員。

如果你從來沒有期望圖中的點數超過5點，那麼你是否真的需要打擾花哨的算法呢？你可以做一個徹底的搜索最好的解決方案。由於唯一的決定是你訪問中間三點的順序，你只需要測試3！ = 6個不同的路徑。即使我誤解了你，並且你想要訪問所有節點的總體最短路徑，那仍然只有5！ = 120個不同的測試路徑（如果距離在兩個方向上相同，則爲60）。