---
# System prepended metadata

title: 'Lab: Shortest Paths'

---

# Lab: Shortest Paths

A$~~~~~~~~~A~~~~~~~~~~~~~~~0$
B$~~~~~~~~~AB~~~~~~~~~~~~1$
C$~~~~~~~~~ABC~~~~~~~~~2$
D$~~~~~~~~~AD~~~~~~~~~~~~1$
E$~~~~~~~~~ABE~~~~~~~~~2$
F$~~~~~~~~~ABCF~~~~~~3$
G$~~~~~~~~ADG~~~~~~~~~2$
H$~~~~~~~~ADGH ~~~~~~3$
I$~~~~~~~~~ADGHI~~~~~4$

b. traversing two nodes will always be greater than or equal to just traversing one.

c. The graph from the previous lab does not obey the triangle inequality, 
example:
 +   HGE = 3 but HE = 12
 +   HFD = 8 but HD = 10

In both cases the inequality does not apply.
d.
A 0 + $\sqrt{8}$
AB 1 + $\sqrt{5}$
AD 1 + $\sqrt{5}$

- Choose B

ABC 2 + 2
ABE 2 + $\sqrt{2}$

- Choose E

ABED 1 + $\sqrt{5}$
ABEF 3 + 1
ABEH 3 + 1
- Choose F

ABEFI 4
- Choose FI

Even when c(v) returned the smallest value, combining h(v) helped us find out that that choice was not necessarily the best choice.

e. 
If the heuristic function has a bad property, it might choose a node that is farther away from the goal node than the others, thus ignoring the triangle inequality.


