图搜索算法

我正在寻找具有一些不寻常属性的图算法.

图中的每条边都是"向上"边缘或"向下"边缘.

有效路径可以是无限数量的"向上",然后是无限数量的"向下",反之亦然.然而,它不能多次改变方向.

例如,有效路径可能是A"向上"B"向上"C"向下"E"向下"F无效路径可能是A"向上"B"向下"C"向上"D

找到两个节点之间最短有效路径的好算法是什么？如何找到所有等长的最短路径？

假设你没有任何启发式方法,那么dijkstra算法的变体就足够了.每次考虑新边缘时,都要存储有关其"祖先"的信息.然后,检查不变量(仅一个方向更改),如果违反则返回.

这里的祖先是沿着最短路径遍历到达当前节点的所有边.存储祖先信息的一种好方法是作为一对数字.如果U是向上的,而D是向下的,那么特定边缘的祖先可能UUUDDDD就是这对3, 4.由于不变,你不需要第三个数字.

由于我们使用了dijkstra算法,因此找到了多条最短路径.