### 使用Python实现路径检索算法 路径检索问题是图论中的经典问题之一，涉及寻找两个节点之间的最短路径或其他特定条件下的最优路径。常见的路径检索算法有广度优先搜索（BFS）、深度优先搜索（DFS）、Dijkstra算法和A*算法等。 以下是几种常用的路径检索算法的Python实现： #### 广度优先搜索（BFS） BFS适用于未加权图中最短路径的查找。其实现如下： ```python from collections import deque def bfs(graph, start, goal): queue = deque([(start, [start])]) visited = set() while queue: current, path = queue.popleft() if current == goal: return path if current not in visited: visited.add(current) for neighbor in graph[current]: if neighbor not in visited: queue.append((neighbor, path + [neighbor])) return None ``` 此代码定义了一个`bfs`函数来执行广度优先搜索[^1]。 #### Dijkstra算法 Dijkstra算法用于带权重图中单源最短路径的计算。其实现如下： ```python import heapq def dijkstra(graph, start, goal): priority_queue = [(0, start, [])] visited = set() while priority_queue: cost, node, path = heapq.heappop(priority_queue) if node not in visited: visited.add(node) path = path + [node] if node == goal: return cost, path for neighbor, weight in graph[node].items(): if neighbor not in visited: total_cost = cost + weight heapq.heappush(priority_queue, (total_cost, neighbor, path)) return float('inf'), [] ``` 这段代码展示了如何利用堆优化的Dijkstra算法求解最短路径[^2]。 #### A*算法 A*算法是一种启发式搜索方法，适合解决更复杂的路径规划问题。其实现如下： ```python def heuristic(a, b): return abs(b[0] - a[0]) + abs(b[1] - a[1]) def a_star_search(graph, start, goal): frontier = PriorityQueue() frontier.put(start, 0) came_from = {} cost_so_far = {} came_from[start] = None cost_so_far[start] = 0 while not frontier.empty(): current = frontier.get() if current == goal: break for next_node in graph.neighbors(current): new_cost = cost_so_far[current] + graph.cost(current, next_node) if next_node not in cost_so_far or new_cost < cost_so_far[next_node]: cost_so_far[next_node] = new_cost priority = new_cost + heuristic(goal, next_node) frontier.put(next_node, priority) came_from[next_node] = current return came_from, cost_so_far ``` 这里提供了A*算法的一个基础框架，其中包含了曼哈顿距离作为启发函数的一部分[^3]。 ---