7b. Graph Algorithms

Definition of a shortest path: minimum summed weights for total path

• AKA minimum cost accrued

Djikstra’s

Evaluates distances from source vertex and only proceeds when

• distance of current vertex + weight to next vertex < stored distance of next vertex (initialized to infinity)
• AKA shortest path to next vertex from source
• In other words, proceed if faster than stored distance, otherwise don’t consider
• Store predecessor vertices to keep track of path in $O(n)$ compared to keeping track of entire path for each vertex $O(n^2)$
• Use priority queue for min distances

Edge cases:

• Cannot use with negative edge weight loop (can just go back and forth, reaching -INF distance before continuing)
• Disconnected graph (doesn’t work since doesn’t search whole graph)

Greedy Algorithm

Takes the best option at each step myopically (without looking at future steps)

Minimum Spanning Tree Problem

Input: undirected connected graph with non-negative edge weights Output: subgraph that is spanning (contains all original vertices) and connected and minimizes $w(A)={\sum }_{e\in A}{W}_e$

Approach 1: Take edges out of A for MST

Kruskal’s Algorithm: Build MST from empty

Essentially add edge to MST iff it is a minimum edge weight and does not create a cycle

Cut

Separate vertex set V into two pieces where $V=B\cup B^E$ where neither are empty

Prim’s Algorithm

Build tree by adding the minimum edge weight vertex outside the current tree

Proving Kruskal and Prim correctness

Utilize the Main Lemma with induction

Key idea: maintaining a set of visited verts and their complement

Main Lemma: If there is a cut $B,B^C$ such that $X\cap E(B,B^C)=\varnothing$, then $X\cup \{e\}$ is contained in some MST.

• Where e is a minimum edge weight in $E(B,B^C)$

Basically saying that if X (current tree) can be partitioned into vertices B and vertices not in B, and these edges are not in X, then the minimum edge weight of the remaining choices to add in the MST is in some MST

• I feel like this is obvious
• Basically just says that at some point, the building MST has a minimum edge weight of its remaining edges that connect to unvisited vertices

Choosing edges out of unselected edges (connecting visited verts to unvisited verts)

1. Assume $A=\varnothing$ as the base case as it is contained in every MST