加权无向图上的最长路
我知道Bellman Ford算法使用负权值，但我希望我可以修改我现有的最短路径方法。
共有1个答案
如果图是无向的，那么最长的路径是无限长的，因为你可以任意地向前和向后访问一条边。因此，您应该设置更多的条件，比如：节点只能访问一次，或者图必须是定向的。
使所有权重为负值并运行Dijkstra将产生无限循环。它实际上相当于我刚才在上面解释的。
有关更多信息，我邀请您阅读以下内容:http://en.wikipedia.org/wiki/topology_sorting http://en.wikipedia.org/wiki/travelling_salesman_problem
-
我试图将这个问题概念化，然后为它编写Java代码。我知道这里有一些讨论，但我没有看到很多回答者，所以我想通过写下我的想法来重申这个问题，我希望从你们那里得到一些反馈。谢谢 我的想法：对于每个叶节点，找到从根节点到它的最长路径。对于所有路径，找到最大路径长度 然而，这不就是蛮力吗，对此还有更优雅的解决方案吗？ 我听说过使用Djikstra的负权重算法，但在某些地方它说这只适用于特定情况？我也看到了关
-
我遇到了一个问题，我必须找出给定图形中的最长路径。我有一个边列表（例如，{AB，BC}），它表明在顶点/节点（A，B，C）之间有一条边。现在我想计算出可能的最长路径（不重复顶点），这样它可以覆盖从任何顶点/节点开始的最大节点。 解决这个问题的最佳方法是什么？我必须把它作为一个计划来实施。 我在谷歌上查找最小生成树、Dijkstra的算法等等。但我想不出什么最适合解决这个问题。 任何帮助或阅读参考资
-
我需要找到图中最长的路径基于边权值。对于图像上的图，它应该是4,5,3,2,1（顺序无关紧要），最好的算法是什么？如果您知道，在您的图中，每个节点都有一个对图中任何其他节点的引用（边）。算法应该改变吗？
-
我能够使用这个算法在一个加权DAG中找到最长的路径（使用拓扑排序，然后放松每个边）。我现在的问题是，是否有一个算法来找到DAG的前3个最长的路径？或者，有没有实现这种算法的javascript或java库？
-
给定一个无权无向图的邻接矩阵，是否有一种有效的方法（多项式算法）来扩展或增加任意给定的两个结点s和T之间的最短路径长度？ 示例： 在下面的例子中，从顶点S=1到顶点T=5有5条不同的“最短路径”，每个路径的长度为3。我想去除最少的边数，这样最短的路径长度被迫变成4或更多。（断开图形连接是可以的。） 表示此图形： 强制最短路径长度从3增加到4的最小代价是去除两条边（1,2）和（5,9） 目标：
-
解决这个问题的正确方法是什么？还能在线性时间内求解吗？