图搜索算法？
图搜索算法？
提问于 2018-06-26 07:51:09
我正在寻找具有一些不寻常特性的图算法。
图中的每条边都是“上”边或“下”边。
一条有效的路径可以有无限数量的“向上”，随后是无限数量的“向下”，反之亦然。但是它不能多次改变方向。
例如，一个有效的路径可能是“向上”B“向上”C“向下”E“向下”F无效路径可能是A“向上”B“向下”C“向上”D
找到两个节点之间最短有效路径的好算法是什么？那么找到所有等长最短路径呢？
回答 2
Stack Overflow用户
发布于 2018-06-26 16:43:56
假设你没有任何启发式，dijkstra算法的变体应该足够好。每当你考虑一个新的边缘，存储关于它的“祖先”的信息。然后，检查不变量（只有一个方向改变），如果违反了原路返回。
这里的祖先是所有沿着最短路径到达当前节点的边界。存储祖先信息的一种好方法是将数字作为一对数字。如果U上升，而D下降，则特定边缘的祖先可能是UUUDDDD，这将是这一对3, 4。由于不变，你不需要第三个数字。
由于我们已经使用了dijkstra算法，所以找到多条最短路径已经被处理了。
Stack Overflow用户
发布于 2018-06-26 17:28:26
也许你可以将你的图转换成一个正常的有向图，然后使用现有的算法。
一种方法是将图分成两个图，一个图具有所有的上边，一个具有所有的下边，并且图1上的所有节点与图2上的对应节点之间具有有向边。
首先求解从图一开始到结束于图二，然后反过来，然后检查最短解。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/-100000351
复制相关文章
相似问题