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