Algorithms - shivamvats/notes GitHub Wiki

Graph Search

Shortest Path

  1. Positive weights, infinite graph: Dijkstra, A*, etc
  2. Negative weights, loop-free, finite graph: Bellman-Ford
  3. Negative weights, loopy/infinite graph: Not solvable
  4. All pairs: Floyd-Warshall

implementations

Set Coverage

Weighted Minimum Set Cover

Given a collection C of subsets of {1,...,n} and weights corresponding to each subset, find a collection of subsets that covers {1,...,n} and incurs the minimum cost. details1

  1. Greed Approach: Choose a subset that minimizes the cost per element (considering only the uncovered elements). This is ln(k) x OPT in the worst-case, where k is the size of the largest subset.
⚠️ **GitHub.com Fallback** ⚠️