MA515 Homework #8Due Friday, November 181. Give a simple example of a digraph with edge weights for which Dijktra’s algorithmfails when started from a particular vertex of this digraph.2. In a communications network, represented by a digraph, the probability that the edgefrom i to j is operative is pij. The probability that all the edges in any given dipath areoperative is the product of the edge probabilities. How can one solve the problem offinding a most reliable dipath from one designated vertex to all of the others? Justifyyour answer.3. Suppose a digraph is given with nonnegative capacities cijassigned to the edges. Thecapacity of a dipath is define d to be the minimum of the capacities of its edges. Howcan one solve the problem of finding maximum capacity dipaths between every pair ofvertices? Justify your answer.4. Suppose we are working with matrices with entries in R ∪ {∞}. Define a new type ofmatrix multiplication ⊗ as follows: P = (pij) = A ⊗ B, where pij= mink{aik+ bkj}.That is, let ordinary addition take the place of multiplication and minimization takethe place of addition.(a) Show that ⊗ is associative. What is the identity matrix?(b) Let C = (cij) be the matrix of edges weights of a complete digraph, setting cii= 0for all i. Prove that the (i, j)-entry of Cm, where Cmis computed according tothe definition of ⊗, is the weight of a minimum weight (i, j)-diwalk, subject to thecondition that the diwalk contains no more than m edges. This is true whetheror not the digraph contains any negative dicycles.5. A certain project consists of a set of tasks to be performed. Denote the set of tasksby {1, . . . , n}. Each task j requires a certain amount of time aj(assumed to be non-negative). For each task j there is a certain subset of tasks Sj⊆ {1, . . . , n} \ {j} thatmust be completed some time before task j is begun. For simplicity, assume that task1 must be completed before all other tasks are begun, and that all other tasks mustbe completed before task n is begun. (I.e., task 1 is the initial task and task n is thefinal task.)(a) Using unrestricted variables tjto represent the time that task j is begun, andthe objective function tn− t1, write a linear program to solve the problem ofdetermining the minimum amount of time required to complete the entire project.1(b) Prove that the dual linear program is a max weight dipath problem in a certaindigraph. (If it isn’t, try another formulation of the primal problem.)(c) Prove that the shortest completion time equals the weight of a maximum weightdipath between two certain vertices in the