Next: Wireless Interference Zones Up: No Title Previous: Formatting HTML Text

Web Reliable

You are the chief network designer for Web Reliable, yet another new ISP that will revolutionize the web as we know it. Web reliable promises to transform the current world-wide-wait into a usable functioning information infrastructure. Their claim is simple: Web reliable provides the most reliable network paths. How? Well, thats where you come in.... The marketing people got a bit carried away and have started a huge ad. campaign without all the technical problems being completely solved. The research lab has come up with a way to find out how reliable each network link in the Web reliable network is. Your job is to use that information and deliver on the Web reliable promise, i.e., find the most reliable paths.

• Since you have signed all the non-disclosure agreements, Web reliable will give you a complete ``map'' of their network. As usual, this network will consist of a set of nodes (routers) and a set of edges (links). Of course, you will also have the information about the failure probabilities of each link.
• The Web reliable network consists of n routers, (numbered 0 ...n-1). All the Web reliable servers are connected to router 0. Since data comes from the Web reliable servers, you will only have to find the most reliable path from router 0 to all the other routers.
• If you find two paths with the same reliability, you should choose the path with the smaller number of hops (i.e. you should choose the path that uses lesser number of links). If you find paths with the same number of hops and the same reliability, you should produce the lexicographically smallest path. For example, if at any point, you could have taken a path through router a and router b, you should choose a if and only if a ;SPMlt; b. (Recall that router ids are non-negative integers). An example of this tie-breaking rule is given later.

Input Format

The input to your program is a description of the Web reliable network

3 3
0 1 0.5
0 2 0.9
1 2 0.5

The network described by the input file corresponds to the network shown in Figure 2.

  
Figure 2: Sample network

The first line lists the total number of nodes in the network, and the total number of edges. Each remaining line consists of two node numbers n m (representing a edge between n and m) and the probability the edge may fail.

Edges are bi-directional: they are specified by a pair of nodes and a probability of failure. The probability of failure is a floating point number in the range (0,1]. Thus, the first line 0 1 0.5 means that there is a link between routers 0 and 1 with probability of link failure equal to 0.5.

The number of edges lines must be equal to the number of edges specified in the beginning. Also, the node identifiers must be in the range 0 .. (NUMNODES - 1).

You are guaranteed that there is at least one path from node 0 to every other node. There are no self loops (i.e. an edge starting and ending at the same node).

Output Format

The output of your program is a set of paths and their associated success probabilities from node 0 in the following format:

From node 0 
  to node 1: Prob.(Success) = 0.50, Path: 0 -> 1
  to node 2: Prob.(Success) = 0.25, Path: 0 -> 1 -> 2

Note that in this example, even though there was a direct link from 0 to 2, the most reliable path went through node 1.

Examples

In this example, the path to node 3 goes through node 1 (and not node 2) because {0, 1, 3} is ``lexicographically smaller'' than {0, 2, 3}. Stated differently, the algorithm could choose either 1 or 2 at node 0: it chose 1 since 1 ;SPMlt; 2.

  
Figure 3: Example network

Input:

4 4
0 1 0.5
0 2 0.5
1 3 0.5
2 3 0.5

Output:

From node 0 
  to node 1: Prob.(Success) = 0.50, Path: 0 -> 1
  to node 2: Prob.(Success) = 0.50, Path: 0 -> 2
  to node 3: Prob.(Success) = 0.25, Path: 0 -> 1 -> 3

Test data used in judging

Input 1	Output 1
Input 2	Output 2
Input 3	Output 3

Our Solution

Next: Wireless Interference Zones Up: No Title Previous: Formatting HTML Text