Differences

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

--- courses:cs211:winter2011:journals:david:chapter6 [2011/03/30 02:29] – [6.8 - Shortest Paths in Graphs] margoliesd
+++ courses:cs211:winter2011:journals:david:chapter6 [2011/04/06 03:26] (current) – [6.10 - Negative Cycles in a Graph] margoliesd
@@ Line 54: / Line 54: @@
 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.