包含n個節點的最佳圖形路徑

是否存在一個確定的算法，用於在有正確訪問N個節點的特定加權圖中找到從點A到點B的路徑，但不一定特別需要任何節點？包含n個節點的最佳圖形路徑

2011-02-08 Robert Toth

我打算假設您正在嘗試用N個節點找到最短/最長的權重。這可能不是最優的，但是從您的原始圖中，您可以生成一個狀態圖，其中包含'N *（＃Nodes）'節點，它們包含原始節點和步驟數，並通過一些最短路徑算法運行，如http://en.wikipedia.org/wiki/Dijkstra 「s_algorithm。

即

A->B->C 
\___/

變得

(A,0)->(B,1)->(C,2) 
    \>(C,1)

你的目標節點將隨後是節點（B，N） - B與N個步驟。如果它不是DAG（（X，0） - >（Y，1） - >（X，2）），則此方法將允許原始圖形中的循環。

來源

2011-02-08 21:59:30 dfb

我遇到的問題是有多條路徑連接特定的節點，所以它不僅僅是A-> B-> C對A-> D-> C，它更多地沿着A-1的線 - > B-3-> C對A-2-> B-1-> C – 2011-02-08 23:32:20

我不太清楚我明白你在說什麼，但讓我澄清一下 - 對於原始圖中的每個節點T ，我們生成N個節點（T，0），（T，1），（T，2）...（T，n）`。對於原始圖中的每條邊T> Y，我們在'（T，k）'和'（Y，k + 1）'之間創建一條邊。對於所有的K.因此，通過圖的路徑應該總是上升一個'（A，0） - >（B，1） - >（D，2）'等。 – dfb 2011-02-08 23:46:40

此問題被稱爲NP-硬通過從Hamiltonian path減少。特別是，你可以用一個多項式時間的方法解決哈密爾頓路徑問題，如下所示：對於有n個節點的圖中每個可能的節點對（s，t），詢問是否存在從s到t的路徑通過正好n個節點。這隻對您的求解器進行多項式調用，所以任何多項式時間解決方案都會導致Hamiltonian路徑問題的多項式時間解決方案。

因此，總之，除非P = NP，否則不應該期望多項式時間算法用於這個問題。

來源

2011-02-08 22:16:15 templatetypedef

我不確定我是否正確說明了它，你可以進行深度優先搜索（距離源頭N-1層）？

如果您可以在該圖層中訪問您的目的地。你可以在那裏找到一條路。

來源

2011-02-12 02:20:05 Wei

包含n個節點的最佳圖形路徑

回答

相關問題