Heterogeneous systems present exciting new oppor- tunities for graph and Machine Learning applications. This paper presents a novel approach for the All-pairs Shortest Path (APSP) computation using a heterogeneous CPU-FPGA Accelerator sys- tem. It is based on a recursive variant of Kleene’s APSP algorithm. Carefully re-engineering the algorithm to exploit parallelism in both the Floyd-Warshall algorithm and the general Kleene algorithm to perform Floyd-Warshall and Matrix-Multiply on the FPGA while the CPU efficiently balances the communication and computation between the kernels, improves state-of-the-art performance on FPGAs for APSP, while achieving near-GPU levels of performance, with less power and hardware resources, and out- performs the CPU-only solution by over 137x for a 8192x8192 problem size. When adjusted for power draw differences in process nodes, it also surpasses the GPU implementation in terms of performance per Watt by over 13%.