Shortest Path Computation Using Minimum Spanning Tree in FPGA

Abstract

The need for speedy execution is mounting in every field and almost all the application.
Hence this utmost requirement in fields like routing wireless sensor nodes, Transportation network,
mobile networks, etc can be quenched by the shortest path Computation. Because of the advantages
of FPGA in terms of low cost, high computational power, they are used for calculating shortest path
between several entities nowadays. The shortest path computation finds its relevance in the utility of
minimum spanning tree algorithmswhichcomprises vagaries of renowned algorithms.The presented
work accosts the use of prim and krushkal algorithm which prevails the greedy approach to find the
desired result.The design envisages the performance of the system with consideration of 3, 6, 10, 20
and 40 nodes in Xilinx software.Along with that the power estimation and area occupancyis procured
in cadence tool. Moreover, the hardware implementation has been carried out in Spartan3E.