2. (10pts) We are given a communication network that is an edge-weighted graph G=(V, E). The...

  

Transcribed Image Text:

2. (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 0 (|E|log |E|) time algorithm to find the most reliable path between two given nodes. Describe its pseudo code, correctness proof and running time proof. (Note: Understand correctly what the question states. On the graph in the figure: 0.4 The path {S, X, T} does not fail with the probability 0.9x0.4 0.36 = 36% S 09 10.9 0.8 - The path {S, X, Y, T} does not fail with the probability 0.90.99.8= 0.64 = 64% Try {S, Y, T} and {S, Y, X, T} to conclude {S, X, Y, T} is the most reliable path.) - 2. (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 0 (|E|log |E|) time algorithm to find the most reliable path between two given nodes. Describe its pseudo code, correctness proof and running time proof. (Note: Understand correctly what the question states. On the graph in the figure: 0.4 The path {S, X, T} does not fail with the probability 0.9x0.4 0.36 = 36% S 09 10.9 0.8 - The path {S, X, Y, T} does not fail with the probability 0.90.99.8= 0.64 = 64% Try {S, Y, T} and {S, Y, X, T} to conclude {S, X, Y, T} is the most reliable path.) -