All pairs reachability
1. Binary search tree
2. Prim's algorithm
3. Kruskal's algorithm
4. Dynamic programming
5. Levenshtein distance
Single source shortest paths
6. Dijkstra’s (Shortest path)
7. Bellman-Ford
Shortest Paths for DAG
8. Topological sort
Single-Source shortest paths
Unweighted graphs
Weighted graphs
9. Dijkstra’s algorithm(negative weight)
All-pairs shortest paths
10. Floyd-Warshall
11. Johnson’s algo for sparse graphs
MULTIPLE SOURCE SHORTEST PATH (SSSP)
5 Dijsktra's algorith
6 Bellman-Ford algorithm
MULTIPLE SOURCE SHORTEST PATH (MSSP)
8 Floyd-Warshall Algorithm
it computes transitive closure (reachability through indirect paths) across all pairs of nodes, capturing relationships
like:
● 1 < 5, 5 < 4 imply 1 < 4.
● 1 < 6, etc., through indirect relationships.
Dynamic programming:
Compute the optimal solution from [a][b] via c ⇒ [c][a][b], we’ll already have computed the optimal
solution from [a][c] and [c][b]
for (int i = 0; i < n; ++i)
adj[i][i] = 0;
for (int k = 0; k < n; ++k)
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
9 Johnson’s Algorithm for Sparse Graphs
1. Binary Search Tree:
Binary Tree level order traversal:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root){return ans;}
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int level = q.size();
vector<int> v;
//now start traversing within level
for (int i=0; i<level;i++){
//Grab, pop, push, add
TreeNode* grab = q.front();
q.pop();
if (grab->left){q.push(grab->left);}
if (grab->right){q.push(grab->right);}
v.push_back(grab->val);
}
ans.push_back(v);
}
return ans;
}
Validate Search Tree
Kth Smallest Element in a BST:
void in(TreeNode* root, vector<int> & arr){
//base case
if(!root){return;}
in(root->left, arr);
arr.push_back(root->val);
in(root->right, arr);
}
int kthSmallest(TreeNode* root, int k) {
vector<int> res;
int(root,res);
return res[k-1];
}
2. Dijkstra’s Algorithm (Shortest Path)
