一個經典的TSP問題的（TSP）的定義是：TSP-Variant，可能的算法？
鑑於加權完整無向圖，其中三角不等式成立返回最小的總重量的漢彌爾頓路徑。
在我的情況下，我不想哈密爾頓路徑，我需要兩個衆所周知的頂點之間的路徑。因此，配方是：
給出一個加權完全無向圖，其中三角不等式成立和兩個特殊的頂點稱爲源和目的地返回訪問所有節點一次，以及從源頭開始和結束到目的地的最小加權路徑。
我記得哈密頓路徑是無向圖中的一條路徑，它只訪問一次頂點。
對於原始問題，Christopher的算法有一個很好的近似值（最差的3/2的最佳解決方案），可以修改我的情況嗎？或者你知道另一種方式？
從成本爲0的目標節點向源節點添加一條邊（=道路），並得到TSP（儘管三角形不等式不成立）。
「追求旅行推銷員」一書簡要提到了這種技巧。
圖形已完成，源和目標之間已經存在邊界。我不確定改變重量是否合理。可以？ – 2013-03-08 18:09:05
我想我明白了這一點。添加一個只有零權重的兩個邊的頂點到源和目標。最後計算新圖上的哈密爾頓路徑。 0重量確保源和目標是連續的。只要刪除額外的節點和相對邊緣，你就有了一個解決方案。 – 2013-03-08 18:18:53
爲什麼不使用dijkstra算法和每個節點上額外的預訂路徑信息。即以最短路徑從源傳遞到該特定頂點的頂點列表。
當你到達你的末端頂點時停下來。那麼你的路徑將是
當前邊+當前邊的起始頂點的路徑。
其中當前邊緣是引導您到達目的地的最後邊緣。
我需要一次訪問所有節點。 – 2013-03-08 18:08:16
你有約束，每個頂點必須只被訪問一次？ – bloops 2013-03-08 17:35:37
........................固定。謝謝。 – 2013-03-08 17:40:31
對於它的價值，指定開始/結束頂點的哈密頓路徑問題的變體有時稱爲「受限哈密頓路徑」。 – mhum 2013-03-08 18:23:25