(20pts. .We are given a communication network that is an edge-weighted graph G (

Question

(20pts. .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: i is the probability that the communication between the two endpoints will not fail. Design an O(IE log IEI) time algorithm to find the most reliable path between two given nodes. Describe its pseudo code, correctness proof and running time proof. 1. (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% The path (S, X, Y, T) does not fail with the probability 0.9×0.9×9.8 0.64 6496 -Try {S, Y, T} and {S, Y, X, T} to conclude {S, X, Y, T} is the most reliable path.) 0.9

Explanation / Answer

SOLUTION:

The below is the algorithm that represents the step by step procedure of the required data;

ALGORITHM(STEP BY STEP PROCEDURE);

àHere at starting from the source 's', sort all the edges incident to 's'. and set the reliable path that is R=

àthen pick the heaviest edge let say that it is having more success probability, R= R {e}

àthen for some 'x' that is the endpoint of the edge 'e' choosen from 's' repeat step 2 recursively for each edge choosen then till we reach the destination 't'.

àhence the output R will be obtained.

àThe Time complexity:

Then from the above algorithm we are sorting the edge set for each time we select an edge.

àtherefore for each we will take at most |E| edges to sort in worst case that is if one vertex is adjacent to rest all .

àThus the overall time complexity is O(Elog E).

àTherefore the algorithm always chooses the path from s to t with largest product of reliability, hence it always gives the correct output.

Therefore our required data is obtained and it is illustrated as above.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.