1.2 ?

First, we can assume we have a function WEIGHT(node, child) where node and child are two nodes in the DAG and there is an edge from node to child. This function simply returns the weight of that edge. Let us denote by infinity some number that is guaranteed to be larger than any number would could encounter in the problem. For instance, it could be 1 more than the sum of the weights of all the edges. Then we can write the following procedure which returns the least cost of any path from an arbitrary node to end: Cost(node) if node is end then return 0 if node has no children then return infinity // Now we compute a set of values one value for each child of node: foreach child of node do if child is end then just compute WEIGHT(node, child) else compute WEIGHT(node, child) + Cost(child) return the minimum of those computed values 1.2 Exercise Prove that Cost(start) does indeed return the least cost of any path from start to end. Hint: First, note that for any node r in our graph G, there might be a number of different paths from 2 to end. However, since G is a finite DAG, there can only be a finite number of such paths, and so there will of necessity be a path of greatest length. (There could be more than one such path, but that doesn't matter.) Be careful: remember that "length" does not mean "cost". By "length" we just mean "the number of edges on the path. It has nothing to do with the weight of the edges. Using that fact, you can prove the result I'm asking for by induction. Here is an inductive hypothesis that you could use: For each integer n > 0, if v is any node in the graph such that the length of any path from v to end is sn, then Cost(v) is the least cost of any path from v to end. This is clearly true for n=0. Go from there. Writing this recursive function is the key to our solution. First, we can assume we have a function WEIGHT(node, child) where node and child are two nodes in the DAG and there is an edge from node to child. This function simply returns the weight of that edge. Let us denote by infinity some number that is guaranteed to be larger than any number would could encounter in the problem. For instance, it could be 1 more than the sum of the weights of all the edges. Then we can write the following procedure which returns the least cost of any path from an arbitrary node to end: Cost(node) if node is end then return 0 if node has no children then return infinity // Now we compute a set of values one value for each child of node: foreach child of node do if child is end then just compute WEIGHT(node, child) else compute WEIGHT(node, child) + Cost(child) return the minimum of those computed values 1.2 Exercise Prove that Cost(start) does indeed return the least cost of any path from start to end. Hint: First, note that for any node r in our graph G, there might be a number of different paths from 2 to end. However, since G is a finite DAG, there can only be a finite number of such paths, and so there will of necessity be a path of greatest length. (There could be more than one such path, but that doesn't matter.) Be careful: remember that "length" does not mean "cost". By "length" we just mean "the number of edges on the path. It has nothing to do with the weight of the edges. Using that fact, you can prove the result I'm asking for by induction. Here is an inductive hypothesis that you could use: For each integer n > 0, if v is any node in the graph such that the length of any path from v to end is sn, then Cost(v) is the least cost of any path from v to end. This is clearly true for n=0. Go from there. Writing this recursive function is the key to our solution