Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |
| courses:cs211:winter2011:journals:anna:chapter_6 [2011/03/29 21:54] – poblettsa | courses:cs211:winter2011:journals:anna:chapter_6 [2011/04/02 21:52] (current) – poblettsa |
|---|
| Our dynamic programming solution is based on the fact that for a graph with no negative cycles, the shortest path has at most n-1 edges, so our optimal solution is opt(i, v). So either the path contains the i-1 edges, in which case opt(i,v) = opt(i-1,v) or the path contains i edges and the first edge is (v,w), in which case opt(i,v) = cost(v,w) + opt(i-1,w). The total solution in opt(n-1,s). The algorithm is given on page 294 and runs in O(n^3) time. We can reduce the running time to O(mn) because, while the graph could have up to n^2 edges, most graphs are much sparser. The space requirement can also be reduced to linear by only keeping track of one value for each node, the length of the shortest path so far, and updating it as we go. Because of less space we have to keep track of each node's first node (after itself) in order to be able to trace the solution back. | Our dynamic programming solution is based on the fact that for a graph with no negative cycles, the shortest path has at most n-1 edges, so our optimal solution is opt(i, v). So either the path contains the i-1 edges, in which case opt(i,v) = opt(i-1,v) or the path contains i edges and the first edge is (v,w), in which case opt(i,v) = cost(v,w) + opt(i-1,w). The total solution in opt(n-1,s). The algorithm is given on page 294 and runs in O(n^3) time. We can reduce the running time to O(mn) because, while the graph could have up to n^2 edges, most graphs are much sparser. The space requirement can also be reduced to linear by only keeping track of one value for each node, the length of the shortest path so far, and updating it as we go. Because of less space we have to keep track of each node's first node (after itself) in order to be able to trace the solution back. |
| |
| | ===6.9 Shortest Paths and Distance Vector Protocols === |
| |
| | A common application of the Shortest Path Problem is routers in a communication network. If the costs on edges represent the delay on a link between two nodes, you can find the minimum delay from s to t. It is possible to make this work by running a protocol to gather global information, but it is better if we can make an algorithm that only needs the information form its neighbors. To update M[v], we only need to know M[w] of its neighbor w. We can potentially terminate the algorithm early because we are only updating values if their neighbor changes, so if no values change, we are done. |
| | |
| | This algorithm is good because it can update at any time and still run, since it does not need all the information from the beginning. If we maintain distances between all nodes, the algorithm is known as a distance vector protocol. The potential problem here is that it comes from a dynamic programming idea that assumes costs are constant. However, edges costs can change, or even be deleted. If this is the case, it can run into a "counting to infinity" problem. This is solved with path vector protocols, which keep track of some representation of the whole path. |
| |
| |
