Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
courses:cs211:winter2011:journals:charles:chapter6 [2011/04/05 05:26] – gouldc | courses:cs211:winter2011:journals:charles:chapter6 [2011/04/05 05:52] (current) – [6.9 Shortest Paths and Distance Vector Protocols] 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. | 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 ===== | ===== 6.8 Shortest Paths in a Graph ===== | ||
- | Problem outline: We want to find the shortest path between two nodes in a directed graph. We cannot use Dijkstra' | + | Problem outline: We want to find the shortest path between two nodes in a directed graph. We cannot use Dijkstra' |
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. | 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. | ||
Line 58: | Line 58: | ||
===== 6.9 Shortest Paths and Distance Vector Protocols ===== | ===== 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' | ||
+ | |||
+ | Problems: Assumes edge costs will remain constant during runtime, which for many reasons will probably not be the case in practice. Also, there is the potential " |