Suppose that you are given a cable network of n sites connected by duplex communication channels. Unfortunately, the communication channels are not perfect. Each channel may fall with a certain probability (also given in the input). One of the n sites is a central station and your problem is to compute the most reliable paths from central station to all other stations (i.e, the paths with the lowest failure probabilities from the central station to all other stations). Design an algorithun to solve this problem. Let w(u,v) denote the failure probability for the channel between u and v.

(30 marks)