```
def BFS(start, end):
global queue
queue.append((start, [start]))
while queue:
node, path = queue.pop(0)
visited.add(node)
if node==end:
return path
for i in G[node]:
if i not in visited:
visited.add(i)
queue.append((i, path+[i]))
```

- Instead of a queue, use a priority queue
- Priority is based on the cost of the path
- Always expand the least costly path

```
G={
0: {1:1, 6:1, 7:4, 8:8, 3:7},
1: {0:1, 2:2, 5:2, 4:1, 6:2},
2: {1:2, 10:2},
3: {0:7},
4: {1:1},
5: {1:2, 10:4},
6: {0:1, 1:2, 9:1},
7: {9:1, 0:4, 8:1},
8: {0:8, 7:1, -1: 1},
9: {6:1, 7:1},
10: {2:2, 5:4, -1: 1},
-1: {8:1, 10:1},
}
```

```
def UCS(G, start, goal):
visited=set()
pqueue=[]
heapq.heappush(pqueue, (0, (0, ())))
while pqueue:
cost, (node, path)=heapq.heappop(pqueue)
if node not in visited:
visited.add(node)
path = path + (node,)
if node==goal:
return path
for neighbour, edgeweight in G[node].items():
if neighbour not in visited:
heapq.heappush(pqueue, (cost+edgeweight, (neighbour, path)))
```

- Mazes - Distance to goal
- 8-puzzle - Number of tiles out of place
- Driving - Straight line distance * constant factor

$h(n) \le c(n \rightarrow n') + h(n')$

```
def astar(G, start, goal):
pqueue=[]
heapq.heappush(pqueue, (H_score(G, start, goal), 0, (start, ())))
while pqueue:
heuristic, cost, (node, path)=heapq.heappop(pqueue)
path = path + (node,)
if node==goal:
return path
for neighbour, edgeweight in G[node].items():
G_score=cost+edgeweight
heapq.heappush(pqueue, (G_score+H_score(G, neighbour, goal), G_score, (neighbour, path)))
```

$f(n') = f(n) \pm \delta$