如何獲得圖中最短的循環路徑？

-1

我正在開發一個簡單的程序來計算從一個城市到另一個城市的最短路徑，使用圖的有向加權節點來表示火車路線圖。如何獲得圖中最短的循環路徑？

到目前爲止，我試過Bellman-Ford，Dijkstra，Floyd-Warshall和Johnson算法和所有的人都好找到不同的目的地是不一樣的起點的最短路徑。

但是當我需要通過其他城市計算城市A和回到城市A之間的路徑時，我總是得到0值，因爲這些方法忽略了從城市到自身的路徑，以便不會被抓到無限循環。

我知道，當它捕獲這個目標節點可能是簡單的通過創建另一個參數是target解決這一問題，循環爲目標的算法停下來，但我沒有技能修改的一個那些圖書館。

任何人都可以告訴我方式嗎？

我的圖是AB5 - BC4 - CD8 - DC8 - DE6 - AD5 - CE2 - EB3 - AE7和B到B的距離應爲9，但在所有這些算法它返回0。

注意：它不是重複的，因爲在我搜索StackOverflow和Google時，至少在Java中搜索路由到目前爲止還沒有發現路由。

來源

2013-08-27 PSyLoCKe

也許你說的是[旅行商問題（http://en.wikipedia.org/ wiki/Travelling_salesman_problem） –

您嘗試過的算法是爲了找到圖形兩個邊之間的最短距離。請參閱@MichaelButscher提到的TSP。 –

從B到B的距離（使用邊BC，CE和EB），OP想要解決[最短路徑問題]（http://en.wikipedia.org/wiki/Shortest_path_problem）（節點之間），這正是[Dijkstra]（http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm）和co的意思！ – OlivierBlanvillain

一個簡單的方法是使用已經具有修改圖的最短路徑算法/庫。您可以複製每個節點和相應的相鄰傳出邊，然後找到從複製節點到原始節點的最短路徑。

這裏是改造會是什麼樣子的AA路徑（不計權爲簡單起見）：

Graphical example

來源

2013-08-27 21:27:12 OlivierBlanvillain

如何獲得圖中最短的循環路徑？

回答

相關問題