---
# System prepended metadata

title: 'Lab: Shortest Paths'

---

# Lab: Shortest Paths 

# Problem: Jump up, Superstar

**a**.

Destination | Path  Cost
\___________________
    A       |  A     0
    B       |  AB    1
    C       |  ABC   2
    D       |  AD    1
    E       |  ABE ADE 2
    F       |  ABCF ABEF ADEF 3
    G       |  ADG   2
    H       |  ABEH ADGH ADEH 3
    I       |  ABCFI ADGHI ADEHI ABEFI ABEHI ADEFI 4
    
**b**.

The triangle inequality says that the shortest path from A to C is less than or equal to the path from A to B added to the path from B to C. 

**c**.

One example is with the edges: eg, gi, and eh.
If we add the weights of edges eg and gi, we find that they are less than the weight of the last edge, eh.
|eg| + |gi| < eh
Where eg has a weight of 2 and gi has one of 1, and eh has a weight of 12.
This defies the logic of the triangle inequality and thus this graph doesn't obey it.

**d**.

Sequence of nodes in the modified algorithm:
A -> E -> I

How did the heuristic function make my search more efficient?

It made getting from vertex A to vertex I much easier. It was also pretty obvious which path would be the shortest as we know the shortest path between to points is a straight line.

**e**.

Discuss why the heuristic function must now overestimate the actual cost of the shortest path. Specifically, what happens to Dijkstra’s algorithm if the heuristic function has this bad property?

As we saw in problem c., the triangle inequality doesn't always hold, therefore it's a good idea to overestimate the cost of the shortest path to ensure that it does hold. When the heuristic function doesn't have this property, Dijkstra's algorithm might sometimes fail to reach the target vertex.
