1. 首页
  2. 问答
  3. 图表最长路径

图表最长路径

2010-03-27 73 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

相关问题

 相关问题