Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | Next revisionBoth sides next revision | ||
| courses:cs211:winter2011:journals:charles:chapter6 [2011/03/30 04:30] – [6.8 Shortest Paths in a Graph] gouldc | courses:cs211:winter2011:journals:charles:chapter6 [2011/03/30 04:41] – [6.8 Shortest Paths in a Graph] 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 ===== | ||
| - | This section is about finding the shortest | + | Shortest |
| - | starting node s and destination node t with minimum | + | 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. |
| - | This section is about using a memoized array to keep track of the shortest paths in a graph. The new method is contrasted with Dijkstra' | + | |
| + | (6.23) //OPT(i,v) = min(OPT(i-1, | ||
