Simplified Algorithm on Network Shortest Path Problem

23. Simplified Algorithm on Network Shortest Path Problem 

ABSTRACT:

An algorithm on the network shortest path problem by gradually eliminating loops on a network is put forward. Using the wagon routing arrowhead line, we start from the origin, plot the routing arrowhead lines in the current loop and the adjacent loops, and decide which edge the arrowhead pointed to should be moved; then according to the structure of the candidate edges to be removed and certain regulations, remove one edge to enlarge the current loop; select the loop nearest to the origin and repeat the above process, until obtain the shortest routing tree taking the origin as its root. The cast study carried out shows that the algorithm is simple, practical, knowable, and suitable for manual searching the shortest route on a simple non-directional network.

Existing System:

• Existing system uses RTF and RTC built up for discretization error along a path.
• Here efficiency of the algorithms directly relates to the magnitude

      of the errors introduced during discretization .

         

 Proposed System:

• In our project we use two techniques to decrease the discretion error.

• Here we use randomized discretization and path delay discretization techniques.

·        The above new techniques either make the link errors to cancel out each       other along the path or treat the path delay as a whole for discretization, which results in much smaller errors.

• The algorithms based on these techniques run much faster than the best existing algorithm

System Requirements:

Hardware:

PROCESSOR          :  PENTIUM IV 2.6 GHz

RAM                      :  512 MB DD RAM

MONITOR             :  15” COLOR

HARD DISK            :  20 GB

CDDRIVE              :  LG 52X

KEYBOARD           :  STANDARD 102 KEYS

                          MOUSE               :  3 BUTTONS

Software:

FRONT END                    :  SWINGS,JFRAMEBUILDER.

OPERATING SYSTEM   :  Window’s Xp

                        BACK END                       : Sql Server  2000

Modules:

• Design of LAN structure
• Finding all possible path
• Time calculation
• Random discrimination

Module Description:

Design of LAN structure:

                        Here we design the structure for which the shortest path is to find .the structure to which we find the shortest path is drawn be

In the data flow diagram.

Finding all possible paths:

Consider a network, where is a set of nodes and is a set of directed links connecting the nodes. The delay and the cost of a link are denoted as and , respectively. The delay and the cost of a path are denoted as and , respectively. and. Let be the length (number of hops) of , and be the length of the longest path in the network. Given a delay requirement, is called a feasible path if . Given a source node, let be the set of nodes to which there exist feasible paths from . For any , the cheapest feasible path from to is defined as The delay-constrained least-cost routing problem (DCLC) is to find the cheapest feasible paths from to all nodes in  which is NP-complete [19]. However, if the link delays are all integers and the delay requirement is bounded by an integer , the problem can be solved in time by Joksch’s dynamic programming algorithm [20] or the extended Dijkstra’s algorithm [17].Joksch’s algorithm is described as follows. , let be a variable storing the cost of the cheapest path from to with , and storing the last link of the path. Initially,and .NIL. Assuming that all link delays are positive, the dynamic programming is given below. Now suppose the link delays are allowed to be zero. We need to add one more step. Let be the sub graph consisting of all zero-delay links. For each , immediately after Joksch’s algorithm calculates , Dijkstra’s algorithm is executed on to improve on zero-delay paths [18].The above polynomials solvable special case with integer delays points out a heuristic solution for the general NP-complete problem with arbitrary delays. The idea is to discretize (scale and then round) arbitrary link delays to integers [15], [17], [18], [21]. There are two existing discrimination approaches, round to ceiling [17] and round to floor [18]. Both approaches map the delay requirement to a selected integer , and then discretize the link delays as follows.

Time calculation

RTC creates negative rounding errors on links. The error accumulates along a path. The accumulated error is proportional to the path length. The larger the topology, the longer a path, the larger the accumulated error. The same thing is true for RTF,which has positive rounding errors on links. In order to achieve -approximation, the accumulated error on a path cannot be too large. To reduce the error on a path, the existing algorithms based on RTC or RTF must reduce the discrimination errors on the links by using a large value. Given the time complexity proportion to .The insight is that if we can reduce the error introduced by discretization without using a larger , we can improve the performance of the algorithm.We develop two new techniques. The first one is called randomized discretization. It rounds to ceiling or to floor according to certain probabilities. The idea is for some links to have positive errors and some links to have negative errors. Positive errors and negative errors cancel out one another along a path in such a way that the accumulated error is minimized statistically. We will prove that, when the following discretization approach is used, the mean of the accumulated error on a path is zero and the standard deviation is bounded . In comparison, the mean of the accumulated error is for RTC and for RTF.

Technique used or algorithm used:

• RANDOMIZED DISCRETIZATION
• PATH DELAY DISCRETIZATION

Advantages:

• Shortest path is found using time.
• Shortest path varies according to the congestion occurred in the path.

REFERENCE:

Xie Jin-bao, “Simplified Algorithm on Network Shortest Path Problem”, IEEE Conference 2011.