COEN 179 Lecture Notes - Lecture 22: Dynamic Programming, Glossary Of Graph Theory Terms
30 May 2020
School
Department
Course
Professor
Document Summary
Coen 179 lecture 22 bellman ford algorithm notes. Input: directed weighted graph (v, e, w) and source vertex s. Output: shortest path from s to t for each t in v. Note: shortest means least total weight, not fewest number of hops no solutions if there are negative weight cycles. Negative weight cycle = -7 e -9 . A fast (o(n lg m)) greedy algorithm due to dijkstra if there are no negative weights. Idea: build a single tree (shortest paths tree) in each step, absorb a new vertex closest to s. Dijkstra s alg may have a wrong answer if there are negative weights (but not negative weight cycles) e es . There is a solution to sssp for this graph. Because this graph has no cycles (and hence no negative weight cycles) Shortest path from s > s : empty path (0) Goal: give a dynamic programming alg for sssp decrease + exhaustive search + caching.
