Concepts8
Proof Techniques for Greedy Algorithms
Greedy algorithm correctness is usually proved with patterns like exchange argument, stays-ahead, structural arguments, cut-and-paste, and contradiction.
Slope Trick
Slope Trick is a technique to maintain a convex piecewise-linear function implicitly using two heaps and a running constant.
Minimum Spanning Tree - Prim
Prim's algorithm builds a Minimum Spanning Tree (MST) by growing a tree from an arbitrary start vertex, always adding the lightest edge that connects the tree to a new vertex.
Johnson's Algorithm
Johnson's Algorithm computes all-pairs shortest paths on sparse graphs by first removing negative edges via reweighting, then running Dijkstra from every vertex.
Dijkstra's Algorithm
Dijkstra's algorithm finds shortest path distances from one source to all vertices when all edge weights are non-negative.
Dijkstra - Variations and Applications
Dijkstra’s algorithm can be adapted to track the second shortest path by keeping the best and second-best distances per vertex.
Topological Sort
Topological sort orders the nodes of a directed acyclic graph (DAG) so every edge points from left to right in the order.
Greedy Algorithms
Greedy algorithms build a solution step by step by always taking the best local choice available.