📗 -> 12/03/24: ECS122A-L16
[Lecture Slide Link]
🎤 Vocab
❗ Unit and Larger Context
Shortest path prob has optimal substructure
Facts
- Paths w more than |v| -1 edges have cycles
- If path/graph has a negative cycle => shortest path problem is undefined
- Can just take cycle infinitely and continue lowering weight
Opt(n-1, V) = shortest path from S to V using at most n-1 edges
= min( OPT(n-2,V), (w(u, v) +OPT(n-2, u)) )
- Can just take cycle infinitely and continue lowering weight
- Add edge or don’t
✒️ -> Scratch Notes
- Log as you go through entry
🔗 -> Links
Resources
- Put useful links here
Connections
- Link all related words