It has been shown that the implementation on a Xilinx Virtex-5 FPGA is more than twice as fast as a
software implementation of the algorithm on a high-end general-purpose processor that runs at an order-of-magnitude faster
clock. The speed-up offered by the design can be further improved by adopting an interconnection topology that maximises
the data transfer rate among the PEs.
1 Introduction
High-speed computation of shortest paths in a graph from a
given source to one or more destinations is a vital requirement
in many application domains such as intelligent transportation
systems, robotics, VLSI computer-aided design and computer
gaming. Highly compute-intensive applications such as urban
traffic simulation typically utilise high-performance
computing systems with powerful general-purpose processors
for fast shortest-path computations. However, in many other
situations, especially in embedded applications, it is not
feasible to utilise powerful general-purpose computing
systems and cost-effective alternatives are desirable. For
instance, cost and energy concerns rule out the use of highend,
high-speed processors in portable navigation devices,
which nevertheless