Concepts7
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.
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.
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.
Priority Queue (Heap)
A priority queue returns the highest-priority element first and is efficiently implemented by a binary heap.