Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2011:journals:chen:chapter_6 [2011/03/30 17:28] – [6.5 RNA SECONDARY STRUCTURE] zhongc
+++ courses:cs211:winter2011:journals:chen:chapter_6 [2011/04/06 16:41] (current) – [6.9 Shortest Paths and Distance Vector Protocols] zhongc
@@ Line 263: / Line 263: @@
+====== 6.8 Shortest Paths in a Graph ======
+Negative weights would change everything that made the Greedy appropriate. Thus we cannot
+make decision only relying on local inforamtion at each step b/c a big negative edge that
+come later may drastically change the picture.
+Some constraints:
+No negative weight cycle
+If some path from s to t contains a negative
+cost cycle, there does not exist a shortest s-t
+path.
+we can loop forever and get ever smaller.
+Reccurence:
+OPT(i,v): minimum cost of a v-t path P using
+at most i edges
+ This formulation eases later discussion
+• Original problem is OPT(n-1, s)
+DP
+ Case 1: P uses at most i-1 edges
+• OPT(i, v) = OPT(i-1, v)
+ Case 2: P uses exactly i edges
+• if (v, w) is first edge, then OPT uses (v, w), and
+then selects best w-t path using at most i-1 edges
+• Cost: cost of chosen edge
+Implementation
+for every edge number,
+for possible node v
+for each edge incident to v
+find out foreach edge (v, w) ∈ E
+M[i, v] = min(M[i, v], M[i-1, w] + cvw )
+O(mn) space.
+General process of DP
+Review: Dynamic Programming Process
+. Determine the optimal substructure of the
+problem  define the recurrence relation
+. Define the algorithm to find the value of the
+optimal solution
+. Optionally, change the algorithm to an
+iterative rather than recursive solution
+. Define algorithm to find the optimal
+solution
+. Analyze running time of algorithms
+Interesting/readable: 8/8
+====== 6.9 Shortest Paths and Distance Vector Protocols ======
+Problem Motivation:
+One important application of the Shortest-Path Problem is for routers in a
+communication network to determine the most efficient path to a destination.
+attempt:
+Dijkstra's algorithm requires global information of network- unrealistic
+we need to work with only local information.
+Bellman-Ford uses only local knowledge of
+neighboring nodes
+ Distribute algorithm: each node v maintains its
+value M[v]
+ Updates its value after getting neighbor’s values
+Problems with the Distance Vector Protocol
+One of the major problems with the distributed implementation of Bellman-
+Ford on routers (the protocol we have been discussing above) is that it’s derived
+from an initial dynamic programming algorithm that assumes edge costs will
+remain constant during the execution of the algorithm.
+That is, we might get into a situation where there is infinite looping of mutual dependancy.
+could fail if the other node is deleted.
+Solution:
+ Each router stores entire path Not just the distance and the first hop
+ Based on Dijkstra's algorithm
+ Avoids "counting-to-infinity" problem and related
+difficulties
+ Tradeoff: requires significantly more storage
+Interesting/readable: 5/5