具有深度优先搜索的最短路径-Java 学习之路

-1

如何使用DFS获取最短路径 . 我已经多次看过这个问题，但回复通常都是使用BFS或不同的算法 . 在机器人穿越迷宫的背景下怎么样？ BFS是不可能的，因为它从节点跳到节点，机器人需要回溯 .

现在我正在尝试使用以下方法解决问题：

def dfs(self, v):
    v.visited = True
    for adj in v.adj:
        if adj.visited is False:
            # set the parent
            adj.successor = v
            # explore the other nodes
            self.dfs(adj)

但是，这并不一定会返回最短路径 . 有没有其他方法来解决这个问题？我已经看到了一些使用深度优先迭代加深的建议，但是我找不到很多实现这个算法的例子 .

1 回答

如果有人对我如何解决这个问题感兴趣，这是我的解决方案：

def dfs(self, v):
    if v.successor is None:  # this is the root node
        v.cost = 0
    v.visited = True
    for adj in v.adj:
        if adj.visited is False:
            # set the parent
            adj.successor = v
            adj.cost = v.cost + 1
            self.dfs(adj)
        # if the cost is less switch the successor
        # and set the new cost
        elif adj.cost > v.cost + 1:
            adj.successor = v
            adj.cost = v.cost + 1
            self.dfs(adj)

这本质上是一个DFS版本，可以跟踪每个顶点的成本 . 如果顶点的成本超过后继1步，则它设置新的后继 . 这允许在不使用BFS的情况下找到最短路径 .

回复于 2024-05-03T16:34:20+08:00

具有深度优先搜索的最短路径

1 回答

相关问题