*(Guest post by Andrew Puleo)*

As professor atri gave us at the end of last lecture, we discussed the shortest path algorithm:

- is the cost of the shortest path that uses edges
- is the shortest path that goes through all neighbors

The shortest path algorithm will search for will ultimately give

**Shortest Path Algorithm:**

- and ,
- For
- For every

- For every

(cost of shortest path from to )

Ex:

Shortest Path s-t:

-3 2

to to $latex t$

**Runtime Analysis:**

- For ()
- For every ()
- ()

- For every ()

Which in total is . Thus, overall runtime is . We can achieve runtime of

**Longest Path Problem:**

Does the longest path have edges? Atri told us this was a trick problem, if you can solve it you’ll get $1 mill

Although if using a witness (a path ) we can check if it is the longest path or not.

Advertisements

## Leave a Reply