Differences

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

--- courses:cs211:winter2011:journals:david:chapter6 [2011/03/30 02:22] – margoliesd
+++ courses:cs211:winter2011:journals:david:chapter6 [2011/04/06 03:26] (current) – [6.10 - Negative Cycles in a Graph] margoliesd
@@ Line 51: / Line 51: @@
 ====6.8 - Shortest Paths in Graphs====
+We will denote our directed graph as G=(V,E) and give each edge a specific weight. While Dijkstra's Algorithm can find us the path of least cost, it does not work for negative costs. Our problem involves finding the path of least cost in a graph that can have negative edge weights, but does not have any negative cycles. If we begin with a greedy approach, we consider the minimum cost edge leaving our node. But this could cause us to miss an edge of greater cost that leads us on a path with more negative costs that could negate it. The Bellman-Ford Algorithm gives an efficient solution to our problem. We note that our path will have at most n-1 edges. If we define opt(i,v) to be the minimum cost of the path from to v to t with at most i edges, we can definite is as the minimum of [opt(i-1,v), min(opt(i-1,w) + the cost of v to w). This gives a 2-dimensional array M with the optimal values for each subproblem. We can get a running time of O(mn). While our array will be of size n<sup>2</sup>, we can actually get a smaller memory requirement. We use a 1-dimensional array and only update a cost if it was lower than the previous cost. We keep a "first" node for each entry to keep track of the first edge we need to take. This will allow us to find the optimal path after the algorithm has completed.
+Readability: 8/10. This was easier to understand than the other sections.
+====6.9 - Shortest Paths and Distance Vector Protocols====
+An application for Shortest Paths algorithm we used in the previous section is for a network of routers (nodes) with direct links (edges). The cost of an edge is the delay of the link and we look for a path with the shortest delay. While Dijkstra's Algorithm could work in this situation because delays cannot be negative, it requires us to have a global knowledge of the network. We can use Bellman-Ford to avoid this problem, but we need to re-implement it as a "push-based" algorithm where costs need only be sent if they change value. We use an "asynchronous" algorithm to denote which nodes are active so we can update its neighbors. We call the finding of distances between all pairs of nodes a "distance vector protocol". One problem with this algorithm occurs if an edge gets deleted. Then our nodes keep referring back to each other until they find a new path. In practice, nodes store more of the entire path so we do not have this problem.
+Readability: 7/10.
+====6.10 - Negative Cycles in a Graph====
+If we augment a graph by adding a sink node that has a path from every other node leading to it and the augmented graph has a negative cycle, then the original graph must have a negative cycle too. If we have a negative cycle and we are looking for a path from one node to the sink that passes through the cycle, as we increase the number of allowable edges, the cycle tends toward negative infinity. However, if there are no negative cycles, then opt(i,v)=opt(n-1,v) as long as i is greater than or equal to n. So as long as this holds true for all nodes, there are no negative cycles in the graph. We can use a pointer graph that starts off having no cycles and add edges to it until we find a cycle.
+Readability: 5/10. The last part confused me.