1. 首頁
  2. 問答
  3. 圖表最長路徑

圖表最長路徑

2010-03-27 113 views
3

如何找到圖表中最長的路徑？我以爲我可以使用深度優先搜索，但我找不到任何更簡單的實施？圖表最長路徑

來源

2010-03-27 iva123

+0

你確定你不是指兩個節點之間的最大距離嗎？ – 2010-03-27 11:49:39

+1

這可能取決於圖的規則和特徵。你允許重新訪問節點嗎？你允許回縮邊緣嗎？該圖可以脫節嗎？它是否被定向？它是無環的嗎？ – 2010-03-27 11:52:11

+0

這似乎是旅行推銷員的變化。它甚至可以解決嗎？ – 2010-03-27 11:56:14

回答

4

由於brainjam在評論中指出這是NP完整。如果圖是非循環的，它只是多項式。如果它的DAG甚至是線性的。請參閱the wikipage瞭解更多信息。

來源

2010-03-27 22:54:06 Karussell

+1

爲一個相當簡單的平面圖很容易實現獲取所有路徑（=>獲取最長的路徑）。看看這裏： http://stackoverflow.com/questions/2500877/count-of-distinct-acyclic-paths-from-aa-b-to-ac-d/2532646#2532646 （並只使用路徑是最長的），這應該給你一個關於如何用一般圖表做的事情的想法：只遍歷當前頂點的所有邊而不是4 nextCell（）調用 – Karussell 2010-03-28 12:02:09

0

保存每個節點爲1 /（您的整數/雙/不管），然後使用最短路徑算法

來源

2011-02-11 22:45:25 ada

+3

我認爲這不會起作用 - 考慮所有邊權重= 1的情況 – gcbenison 2012-04-22 17:43:09

1

如果它是一個DAG G =（V，E），你可以簡單的做一個拓撲排序。

然後您將某個節點標記爲s和t。

然後你可以使用動態編程，其中opt(I)= max(opt(j)+1)其中j邊緣（J，I）是E.

只需設置選擇（S）= 0和他人-INF和S前後忽略節點t的拓撲排序（你不能從s到達這個節點，並且在你傳遞t之後，你不能返回）。

請注意，其工作只適用於DAG（定向非循環圖）。

請注意，如果它不是DAG，那麼您可以將每條邊乘以-1，然後使用Bellman Ford，但是（！）如果您有負循環，它將不起作用。

來源

2014-01-23 14:00:16 member555

相關問題

 相關問題