Techniques for Computing Shortest Path Between Nodes

We present a fast algorithm for computing all shortest paths between source nodes s ∈ S and target nodes t ∈ T. This problem is important as an initial step for many operations research problems (e.g., the vehicle routing problem), which require the distances between S and T as input. Our approach is based on highway hierarchies, which are also used for the currently fastest speedup techniques for shortest path queries in road networks. We show how to use highway hierarchies so that for example, a 10 000 × 10 000 distance table in the European road network can be computed in about one minute. These results are based on a simple basic idea, several refinements, and careful engineering of the approach. We also explain how the approach can be parallelized and how the computation can be restricted to computing only the k closest connections.

Description

Calculating shortest distance in Network is one of the important network functions for QoS routing, MLPS Path selection, ATM networking and traffic networking engineering. In voice and video calling finding cheapest path is not an easy task. In order to find solution for this problem many researches and algorithms are designed. This project proposes two techniques which will reduce decentralization errors and provide shortest routing distance by developing faster algorithms. Providing shortest path is the important factor for successful design in QOS system. Simulator is used to test new techniques which show execution time efficiency in new system.