由于您尝试从两个维度解决此问题，并且除了上述问题之外，还针对其他问题，让我们探索一些更通用的解决方案。我们正在尝试解决有向图上的最短路径问题。

目前a -> [a]，我们对图形的表示类似于，其中函数返回从输入可到达的顶点。另外，任何实现都需要我们进行比较以查看两个顶点是否相同，因此我们需要Eq a。

下图是有问题的，并大致介绍了解决问题的几乎所有困难：

problematic 1 = [2]
problematic 2 = [3]
problematic 3 = [2]
problematic 4 = []

当试图从1达到4时，必须检测到一个涉及2和3的循环，以确定没有从1到4的路径。

广度优先搜索

如果应用于有限图的一般问题，将提出的算法将具有在时间和空间上都不受限制的最坏情况下的性能。我们可以通过添加循环检测来修改他的解决方案，以解决仅包含有限路径和有限循环的图的一般问题。他的原始解决方案和此修改都将在无限图中找到有限路径，但都无法可靠地确定无限图中两个顶点之间没有路径。

acyclicPaths :: (Eq a) => (a->[a]) -> a -> a -> [[a]]
acyclicPaths steps i j = map (tail . reverse) . filter ((== j).head) $ queue
  where
    queue = [[i]] ++ gen 1 queue
    gen d _ | d <= 0 = []
    gen d (visited:t) = let r = filter ((flip notElem) visited) . steps . head $ visited 
                        in map (:visited) r ++ gen (d+length r-1) t

shortestPath :: (Eq a) => (a->[a]) -> a -> a -> Maybe [a]
shortestPath succs i j = listToMaybe (acyclicPaths succs i j)

重用stepWill的答案中的函数作为示例问题的定义，我们可以得到11层建筑中从4楼到5楼的最短路径的长度fmap length $ shortestPath (step 11) 4 5。这返回Just 3。

让我们考虑一个具有v个顶点和e个边的有限图。可以通过大小为n〜O（v +
e）的输入来描述具有v个顶点和e个边的图。此算法的最坏情况图是具有一个不可达的顶点，j其余的顶点和边专门用于创建从开始的最大数量的非循环路径i。这可能就像一个派系，包含所有不是i或的顶点j，且边缘i到并非所有的另一个顶点j。具有e个边的小群中的顶点数为O（e
^（1/2）），因此此图具有e〜O（n），v〜O（n ^（1/2））。在确定该图j不可达之前，该图将具有O（（n ^（1/2））！）条路径进行探索。

在这种情况下，此函数所需的内存为O（（n ^（1/2））！），因为它只需要为每个路径不断增加队列。

在这种情况下，此函数所需的时间为O（（n ^（1/2））！* n ^（1/2））。每次扩展路径时，都必须检查新节点是否不在路径中，这需要O（v）〜O（n
^（1/2））时间。如果我们拥有Ord a并使用一个Set a或类似的结构来存储访问的顶点，则可以将其改进为O（log（n ^（1/2）））。

对于非有限的图形，这个功能应该只是不能确切地终止时不存在从有限的路径i来j但确实存在，从一个非限定路径i来j。

动态编程

动态编程解决方案不能以相同的方式推广。让我们探究原因。

首先，我们将采用chaosmasttter的解决方案，使其具有与广度优先搜索解决方案相同的界面：

instance Show Natural where
    show = show . toNum

infinity = Next infinity

shortestPath' :: (Eq a) => (a->[a]) -> a -> a -> Natural
shortestPath' steps i j = go i
    where
        go i | i == j = Zero
             | otherwise = Next . foldr minimal infinity . map go . steps $ i

这很好地工作电梯的问题，shortestPath' (step 11) 4 5是3。不幸的是，由于我们的问题，shortestPath' problematic 1 4堆栈溢出了。如果我们为Natural数字添加更多代码：

fromInt :: Int -> Natural
fromInt x = (iterate Next Zero) !! x

instance Eq Natural where
    Zero == Zero         = True
    (Next a) == (Next b) = a == b
    _ == _ = False

instance Ord Natural where
    compare Zero Zero         = EQ
    compare Zero _            = LT
    compare _ Zero            = GT
    compare (Next a) (Next b) = compare a b

我们可以问最短路径是否短于某个上限。我认为，这确实显示了惰性评估正在发生的情况。problematic 1 4 < fromInt 100是False并且problematic 1 4 > fromInt 100是True。

接下来，要探索动态编程，我们将需要介绍一些动态编程。由于我们将为所有子问题建立一个解决方案表，因此我们需要知道顶点可以采用的可能值。这给我们一个稍微不同的界面：

shortestPath'' :: (Ix a) => (a->[a]) -> (a, a) -> a -> a -> Natural
shortestPath'' steps bounds i j = go i
    where
        go i = lookupTable ! i
        lookupTable = buildTable bounds go2
        go2 i | i == j = Zero
              | otherwise = Next . foldr minimal infinity . map go . steps $ i

-- A utility function that makes memoizing things easier
buildTable :: (Ix i) => (i, i) -> (i -> e) -> Array i e
buildTable bounds f = array bounds . map (\x -> (x, f x)) $ range bounds

我们可以使用like shortestPath'' (step 11) (1,11) 4 5或shortestPath'' problematic (1,4) 1 4 < fromInt 100。这仍然无法检测到周期…

动态编程和循环检测

循环检测对于动态编程是有问题的，因为从不同路径进入子问题时，子问题并不相同。考虑我们problematic问题的一个变体。

problematic' 1 = [2, 3]
problematic' 2 = [3]
problematic' 3 = [2]
problematic' 4 = []

如果我们试图从获取1到4，我们有两个选择：

• 去2和走的最短路径2，以4
• 去3和走的最短路径3，以4

如果我们选择探索2，我们将面临以下选择：

• 去3和走的最短路径3，以4

我们希望将从3到的最短路径的两种探索结合4到表中的同一条目中。如果我们想避免循环，那实际上是有些微妙的事情。我们面临的问题确实是：

• 去2，并采取从最短路径2，以4不参观1
• 去3，并采取从最短路径3，以4不参观1

选择之后 2

• 去3和走的最短路径3，以4不登陆1或2

关于如何获得这两个问题3，4有两个略有不同的答案。它们是两个不同的子问题，它们不能放在表的同一位置。回答第一个问题最终需要确定你不能去4的2。回答第二个问题很简单。

我们可以为每个可能的先前访问的顶点集创建一堆表，但这听起来不是很有效。我几乎说服了我自己，仅靠懒惰就无法解决动态编程问题。

广度优先搜索Redux

在研究具有可达性或周期检测的动态编程解决方案时，我意识到，一旦我们看到了选项中的一个节点，无论我们是否跟随该节点，访问该节点的后续路径都永远不是最优的。如果我们重新考虑problematic'：

如果我们试图从获取1到4，我们有两个选择：

• 去2，并采取从最短路径2到4无需访问1，2或3
• 去3，并采取从最短路径3到4无需访问1，2或3

这为我们提供了一种算法，可以很容易地找到最短路径的长度：

-- Vertices first reachable in each generation
generations :: (Ord a) => (a->[a]) -> a -> [Set.Set a]
generations steps i = takeWhile (not . Set.null) $ Set.singleton i: go (Set.singleton i) (Set.singleton i)
    where go seen previouslyNovel = let reachable = Set.fromList (Set.toList previouslyNovel >>= steps)
                                        novel = reachable `Set.difference` seen
                                        nowSeen = reachable `Set.union` seen
                                    in novel:go nowSeen novel

lengthShortestPath :: (Ord a) => (a->[a]) -> a -> a -> Maybe Int
lengthShortestPath steps i j = findIndex (Set.member j) $ generations steps i

不出所料，lengthShortestPath (step 11) 4 5是Just 3和lengthShortestPath problematic 1 4是Nothing。

在最坏的情况下，generations需要的空间为O（v * log v），时间为O（v * e * log v）。