SFWRENG 2C03 Study Guide - Midterm Guide: Dynamic Programming, Priority Queue, Transitive Closure

• School: McMaster University
• Department: Software Engineering
• Course: SFWRENG 2C03
• Professor: R. Khedri

Document Summary

The next line is always the shortest (minimum weight) only if it does not create a cycle. The next vertex to be added is always the one lowest weight to the previously discovered vertex. Shortest path from s to every other node, but edges are weighted with no loss of generality. Relaxation: if the shortest path to v is longer than the shortest path that includes u, make the shortest path to v include u. There are 6 properties of shortest paths and relaxation: (page 650) Predecessor: once all estimates are correct, you have a subgraph that is all shortest paths from s. More a checker for shortest path than a finder: checker for negative cycles, dynamic. Line 2: iterate v 1 times (where huge run time comes from) Once you relax all your predecessors, later relaxations will result in a shortest path. Each edge is being visited v 1 times. e. g. page 652.