为此，我应该使用什么图遍历算法？
我需要以某种方式遍历有向图，但我不确定要使用的算法。也许Stackoverflow可以提供帮助。
情况-我有一个有向图，其中的边有一个与它们相关联的数字。让我们假设这个数字是以英尺、英里、……为单位测量的距离。我想从一个起始结点开始遍历，并找到与该起始结点相距一定距离的所有边
例如，我想从某个节点开始，遍历图形，找到从开始到现在走了100英里的每一条边。例如(2)，start_node - edge-1(80英里)->节点(2)- edge-2(40英里)->节点(3)-edge-3(50英里)- start_node - edge-4(40英里)->节点(4)- edge-5(70英里)->节点(5)--edge-6(50英里)--
从start_node开始，行进100英里，答案是edge-2，edge-5。有没有关于我应该使用/考虑的遍历算法的想法？
谢谢
回答 4
Stack Overflow用户
发布于 2010-08-27 02:37:52
我会选择Dijkstra algorithm。当指向最后一个标记节点的路径超过定义时，就停止。
Stack Overflow用户
发布于 2010-08-27 02:37:20
Dijkstra's algorithm。
Stack Overflow用户
发布于 2010-08-27 04:01:41
假设没有一条边可以多次遍历，那么您的问题就是Longest path problem的泛化，这是NP难的。因此，像Dijkstra算法这样的多项式时间方法将不起作用。
如果你的图不是很大，你可以做动态编程:一个表Dv，k，它为每个顶点v和每个边数存储从根到v的所有可能的距离，有k条边，加上每个可能距离的所有可能的前置。如果Dv，k-1被完成，则可以填充Dv，k。您可以重复此操作，直到距离不再低于100，然后可以从成本恰好为100的每个顶点开始回溯。
https://stackoverflow.com/questions/3578313
复制相似问题
腾讯云开发者
