Design And Analysism of Algorithms

Most of the communication networks are related to concept of graphs these days. In such networks, nodes are the cities, or intersections, or server nodes, and the links connect them. We always have various plans to travel from one node to another node such as by car, by flight or routing internet traffic. Basically, our plan should include source, destination and a planned path in between. Here we built up this project by considering road network between cities as a motivating application. We always look for a shortest route when we plan a trip from source (a) to destination (b). Here cities are termed as nodes. Here, there will be traffic as many cars travel and the traffic is assumed to be random. So, we get delayed due to the traffic. This delay, which is rarely constant along an edge is calculated according to the random variable. So, we define our shortest path in terms of a stochastic setting. We call this path as Uncertain Shortest Path.