Differences

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

--- courses:cs211:winter2011:journals:charles:chapter6 [2011/04/05 05:29] – [6.8 Shortest Paths in a Graph] gouldc
+++ courses:cs211:winter2011:journals:charles:chapter6 [2011/04/05 05:41] – [6.9 Shortest Paths and Distance Vector Protocols] gouldc
@@ Line 58: / Line 58: @@
 ===== 6.9 Shortest Paths and Distance Vector Protocols =====
+Outline: An instance of the shortest-path problem on an undirected graph for which all edge costs are positive. Dijkstra's is possible, but we don't want to use it (we can think of something better) because we are talking about routers here and we prefer to work with local information. The BF Algorithm from 6.8 has a local property that can be utilized in a parallel programming solution. If we maintained each node's value in a memoized array, we could update it by simply looking at the values of all of its neighbors and computing the total cost of that value and an edge to that node. This section proposes a change in the BF Algorithm from a "pull-based" implementation to a "push-based" implementation.