python实现对有向图的代价一致搜索代码
时间: 2024-05-10 11:11:10 浏览: 9
在Python中实现对有向图的代价一致搜索可以使用以下代码:
```python
from queue import PriorityQueue
def uniform_cost_search(graph, start, goal):
visited = set()
queue = PriorityQueue()
queue.put((0, start, [start]))
while not queue.empty():
cost, node, path = queue.get()
if node == goal:
return path
if node not in visited:
visited.add(node)
for neighbor, edge_cost in graph[node].items():
if neighbor not in visited:
total_cost = cost + edge_cost
queue.put((total_cost, neighbor, path + [neighbor]))
return None
```
这段代码使用了优先队列来实现代价一致搜索。它接受一个有向图 `graph`、起始节点 `start` 和目标节点 `goal` 作为输入,并返回从起始节点到目标节点的最佳路径。