(10pts) We are given a communication network that is an edge-weighted graph G-(V, E) The weight on each edge is at least 0 and at most 1, representing the reliability of the communication channel: it is the probability that the communication between the two endpoints will not fail. Design an O(E| log lEl) time algorithm to find the most reliable path between two given nodes. Describe its pseudo code, correctness proof and running time proof. 2. (Note: Understand correctly what the question states. On the graph in the figure: - The path {S, X, T} does not fail with the probability 0.9x0.4 0.36-36% 0 The path (S, X, Y, T does not fail with the probability 0.9x0.9x9.8-0.64-6490 -Try {S, Y, T} and {S, Y, X, T} to conclude {S, X, Y, T} is the most reliable path.) 0.9 0 (10pts) We are given a communication network that is an edge-weighted graph G-(V, E) The weight on each edge is at least 0 and at most 1, representing the reliability of the communication channel: it is the probability that the communication between the two endpoints will not fail. Design an O(E| log lEl) time algorithm to find the most reliable path between two given nodes. Describe its pseudo code, correctness proof and running time proof. 2. (Note: Understand correctly what the question states. On the graph in the figure: - The path {S, X, T} does not fail with the probability 0.9x0.4 0.36-36% 0 The path (S, X, Y, T does not fail with the probability 0.9x0.9x9.8-0.64-6490 -Try {S, Y, T} and {S, Y, X, T} to conclude {S, X, Y, T} is the most reliable path.) 0.9 0