graph-theory - 图搜索算法

Question

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

图中的每条边要么是“上”边，要么是“下”边。

一条有效的路径可以经过无限数量的“向上”，然后是无限数量的“向下”，反之亦然。然而，它不能多次改变方向。

例如，一个有效的路径可能是 A “up” B “up” C “down” E “down” F
无效的路径可能是 A “上” B “下” C “上” D

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

Answer 1

假设您没有任何启发式方法，dijkstra's algorithm 的变体应该足够了。每次考虑新的边缘时，请存储有关其“祖先”的信息。然后，检查不变量(只有一个方向变化)，如果违反则回溯。

这里的祖先是沿着最短路径到达当前节点的所有边。存储祖先信息的一种好方法是将其存储为一对数字。如果 U 向上，D 向下，则特定边的祖先可能是 UUUDDDD ，这将是对 3, 4 .由于不变量，您将不需要第三个数字。

由于我们使用了 dijkstra 算法，因此已经解决了寻找多个最短路径的问题。