---
# System prepended metadata

title: 'Lab 16, Shortest Paths, Nick Cardenas and Sam Larsen'

---

# Lab 16, Shortest Paths, Nick Cardenas and Sam Larsen
## Problem: Jump Up Superstar

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

b. The triangle inequality is saying that in any triangle of nodes where each is connected to each other, the shortest path is always a direct path between two nodes instead of a path of two edges.

c. The graph from our previous lab does not obey this inequality because there are multiple triangles where the edge connecting two vertices is not the shortest path between them. For example, in triangle HEG, the shortest path from H to E is HG->GE and not just HE

d. The least distance possible is to chose A as our vertex. This makes it so we do not move from A and take the straight line from A to H which is equal to the square root of 8. We tried A-A then A-H, A-B then B-H, A-B-E then E-H, and A-B-E-H then H-I. The straight line will always be the most efficient becuase of the pythagrian theorum, which states that $a^2+b^2 = c^2$, so the length c will always be less than the sum of the component edges.

e. The heuristic function may overestimate the cost of the shortest path in the case where the triangle inequality does not hold. Then, the function would think the direct edge between two nodes is the shortest path, and then Dijkstra's algorithm would produce an inaccurate path.