We have the following weighted directed acyclic graph (DAG) that has seven nodes named . The weight of all edges is equal to 1.
(1) List all of the shortest paths from to .
(2) Answer the number of directed paths from to .
Suppose we have a simple connected weighted DAG with a set of nodes and a set of edges . The weight of all edges is equal to 1. For any node , let . Note that indicates an edge from to . We suppose is the only node whose is an empty set.
(3) For any node , let denote the number of paths from to , and let . Express using elements of .
(4) For any node , let denote the length of the shortest path from to , and let . Express using elements of .
Let be the set of all non-negative integers and . We define a total order of two elements in as if and only if or the rightmost non-zero component of is negative. For example, , , and .
For a given , consider the task of listing all elements in following the order , that is, listing all elements in as
so that holds for all .
Both Algorithm 1 and Algorithm 2 on the next page are for accomplishing the task with a min-heap for keeping elements in , where "min" means minimum in the order . Note that "Insert into " means to insert into as its root and to maintain so that it keeps the heap property. Also, "Extract from " means to remove from and to maintain so that it keeps the heap property.
(1) Draw the heap of Algorithm 1 as a tree, not an array, obtained after executing the part ① for the case . Also illustrate step by step how is maintained in the first repetition of the while loop.
(2) Fill \phantom{space} in Algorithm 2 so that the size of is no more than in the while loop.
(3) For the case , illustrate step by step how is maintained in the first and second repetitions of the while loop in Algorithm 2.
(4) Let . Explain the reason why Algorithm 2 with your answer for (2) works as requested.
