Concepts9
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.
Kinetic Tournament Tree
A kinetic tournament tree maintains the minimum (or maximum) of moving values whose pairwise order can change over time.
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.