logo标签列表

我该使用哪种图遍历算法来解决这个问题？

algorithm
3
我需要按照特定的方式遍历一个有向图，但不确定要使用哪种算法。或许Stackoverflow能够提供帮助。
情况如下： - 我有一个有向图，边缘上有一个与之相关联的数字。假设这个数字是以英尺、英里等为单位的距离。 我想从起点开始遍历，并找到所有距离起点一定距离的边缘。
例如，我想从某个节点开始遍历图形，并找到每条边缘，其中我已经从起点行驶了100英里。 例如（2）， start_node ---- edge-1(80 miles) ---> node(2) ---- edge-2(40 miles) ---> node(3) ---edge-3(50 miles) --- start_node ---- edge-4(40 miles) ---> node(4) ---- edge-5(70 miles) ---> node(5) ---edge-6(50 miles) ---
从start_node开始行驶100英里，答案将是edge-2、edge-5。 您认为我应该使用/考虑哪种遍历算法呢？
谢谢。
4个回答
3
我会选择 Dijkstra算法。当到达最后一个标记节点的路径超过定义时，停止搜索。
Dijkstra算法不是找到A和B之间的单一最短路径吗？我想知道长度为N的“所有”路径的结束边缘。我已经有一段时间没有看过这个算法了，但我认为它只能找到单一最短路径。 - BobL
在我的情况下，我不知道终点顶点。 - BobL
2
迪杰斯特拉算法。
2
假设每条边只能遍历一次，您的问题是最长路径问题的推广版本，是NP难问题。因此，像Dijkstra算法这样的多项式时间复杂度方法是不适用的。
如果您的图形不是非常大，可以使用动态规划方法：一个表格D[v，k]，存储每个顶点v和每个边数的所有可能距离，从根节点到具有k个边的v的所有可能距离，以及每个可能距离的所有可能前任。如果D[v，k-1]已经完成，则可以填充D[v，k]。重复此过程直到没有距离低于100，然后您可以从每个达到恰好100成本的顶点开始回溯。
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接