Feb 21, 2012
Minimum Spanning Tree / Shortest Path
Minimum Spanning Tree
Prim’s(running time: ElogV): Arbitrary vertex -> select shortest edges from all possible vertices Kruskal’s(ElogV): Select shortest edges in ascending order
Shortest Path
Dijkstra (greedy, ElogV): set all vertices’ distances to ∞ -> relax minimum weight vertices when all possible edges checked Bellman Ford (Dinamic Programming, EV):
- Can handle negative edge if there are no negative cycles, edges at most V-1
- First, relax all vertices in |V|-1 time
- Detecting negative cycles: run for n iteration(instead of n-1)
◦ Add t with 0 cost edge to all nodes-> check OPT(n,v) = OPT(n-1, v) for all nodes
