lecture14.pdf
web.stanford.edu · 3,216 words · saved by 1 readers
N/A
CS 161 Lecture 14 – Amortized Analysis Jessica Su (some parts copied from CLRS) 1 Bellman-Ford Algorithm The Bellman-Ford algorithm is a way to find single source shortest paths in a graph with negative edge weights (but no negative cycles). The second for loop in this algorithm also detects negative cycles. The first for loop relaxes each of the edges in the graph n − 1 times. We claim that after n − 1 iterations, the distances are guaranteed to be correct. Overall, the algorithm takes O(mn) time. 1.1 Correctness To prove correctness, we reformulate the algorithm in…
saved by
related reading
- Bellman–Ford Algorithm - GeeksforGeeksgeeksforgeeks.org
- pasa.pdfmipmip.org
- Lecture 19: Dynamic Programming I: Fibonacci, Shortest Pathsyoutube.com
- Competitive Programmer's Handbookcses.fi
- Lecture 14: Zero knowledge proofsboazbarak.org
- 1404.5236 Sum-of-Squares Proofs and the Quest toward Optimal Algorithmsarxiv.org
- The hidden beauty of the A* algorithmyoutube.com
- prox_algs.pdfweb.stanford.edu
- eecs127_reader.pdfeecs127.github.io
- Lecture 20: Amortized Analysiscs.cornell.edu
- Tim Roughgarden's Lecture Notestimroughgarden.org
- CSC 151 - Analyzing procedureseikmeier.sites.grinnell.edu