只檢查兩個節點是否在給定距離（路徑長度）在一個圖表

Question

我試圖實現一個python函數，它檢查兩個給定節點（start和goal）是否在一定距離內（假設dist = 4 ）在圖中。

一個原始的方法是找到兩個節點之間的最短路徑（使用Breadth First Algorithm），然後檢查最短路徑的長度是否小於（或等於）規定的距離（dist = 4）。但是，這顯然不是最好的解決方案，並且有很多開銷。從這兩個python函數開始，請你指導我如何修改這些函數來實現這樣的功能？

正如我所提到的，我對找到的路徑本身並不感興趣。我們所有的興趣在於兩個節點是否彼此規定的距離在內。 A YES或NO返回標誌應該就足夠了。

def bfs_paths(graph, start, goal): 
    queue = [(start, [start])] 
    while queue: 
     (vertex, path) = queue.pop(0) 
     for next in graph[vertex] - set(path): 
      if next == goal: 
       yield path + [next] 
      else: 
       queue.append((next, path + [next])) 

def shortest_path(graph, start, goal): 
    try: 
     return next(bfs_paths(graph, start, goal)) 
    except StopIteration: 
     return None 

Answer 1

您不必找到它們之間的最短距離。你所要做的就是在需要的dist後切斷你的bfs。如果您在截止前未訪問目標節點，則開始與目標之間的距離超過dist。你也可以用類似的方式使用dfs。在深度大於dist時切斷搜索。這種搜索方法稱爲深度限制搜索。