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
- Competitive Programmer's Handbookcses.fi
- Lecture 20: Amortized Analysiscs.cornell.edu
- Visualizing Algorithmsbost.ocks.org
- Dijkstra's algorithm - Wikipediaen.wikipedia.org
- Structure and Interpretation of Computer Programsmitp-content-server.mit.edu
- Computer Scientists Establish the Best Way to Traverse a Graph | Quanta Magazinequantamagazine.org
- Main Page - Algorithms for Competitive Programmingcp-algorithms.com
- pasa.pdfmipmip.org
- Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowellbigocheatsheet.com
- Algorithm - Wikipediaen.wikipedia.org
- CSC 151 - Analyzing procedureseikmeier.sites.grinnell.edu