Differences

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

--- courses:cs211:winter2011:journals:charles:chapter6 [2011/03/30 04:41] – [6.8 Shortest Paths in a Graph] gouldc
+++ courses:cs211:winter2011:journals:charles:chapter6 [2011/04/05 05:26] – gouldc
@@ Line 51: / Line 51: @@
 We do this by incorporating divide-and-conquer principles into our algorithm. I'm slightly confused by the divide-and-conquer component to this problem. In class we did it with the graph in Figure 6.19. We started in the top left and found the shortest path to some midpoint, then we did the same thing from the bottom right. I will need to look in more depth at the pseudo-code on page 288 to get a better grasp of the concept.
 ===== 6.8 Shortest Paths in a Graph =====
-Shortest path in a directed graph where negative edges are possible. For this reason Dijkstra's Algorithm doesn't always work. (We cannot grow the blob, but we can build up partial solutions under the constraint that we can only use i edges.) In this problem we assume there are no negative cycles (cycles that decrease the total cost of the path); otherwise you could follow the cycle infinitely many times and reduce the cost to negative infinity.
+Problem outline: We want to find the shortest path between two nodes in a directed graph. We cannot use Dijkstra's Algorithm, however, because now there can be negative weights. (We won't know that we have grown the blob in the right way, because there could be a negative edge in the future that provides a shorter path to some node already in the blob.) Therefore we want to build up partial solutions. The first partial solution is the cost of s->t that uses at most one edge; if s doesn't have an edge to t, then the value we put in the memoized array is infinity. (6.22) says that the longest possible optimal path has n-1 edges. So at most we would do n-1 iterations of this.
-We want the path from s -> t that minimizes the total edge costs but that uses at most i edges. (6.22) says that the longest possible optimal path has n-1 edges.
+Here we assume no negative cycles because otherwise the optimal path would follow that cycle infinitely many times and so reduce the cost of the path to negative infinity. But that would be stupid. We saw from class that like the problem above we can fill any column by referring only to the column itself and the column that came before it.
-(6.23) //OPT(i,v) = min(OPT(i-1,v), min_w(OPT(i-1,w) + cw))//
+(6.25) says that the shortest path algorithm can run in O(mn) time.
+===== 6.9 Shortest Paths and Distance Vector Protocols =====