On the Energy Behaviors of the Bellman–Ford and Dijkstra Algorithms: A Detailed Empirical Study

Abstract

The Single-Source Shortest Paths (SSSP) graph problem is a fundamental computation. This study attempted to characterize concretely the energy behaviors of the two primary methods to solve it, the Bellman–Ford and Dijkstra algorithms. The very different interactions of the algorithms with the hardware may have significant implications for energy. The study was motivated by the multidisciplinary nature of the problem. Gaining better insights should help vital applications in many domains. The work used reliable embedded sensors in an HPC-class CPU to collect empirical data for a wide range of sizes for two graph cases: complete as an upper-bound case and moderately dense. The findings confirmed that Dijkstra’s algorithm is drastically more energy efficient, as expected from its decisive time complexity advantage. In terms of power draw, however, Bellman–Ford had an advantage for sizes that fit in the upper parts of the memory hierarchy (up to 2.36 W on average), with a region of near parity in both power draw and total energy budgets. This result correlated with the interaction of lighter logic and graph footprint in memory with the Level 2 cache. It should be significant for applications that rely on solving a lot of small instances since Bellman–Ford is more general and is easier to implement. It also suggests implications for the design and parallelization of the algorithms when efficiency in power draw is in mind.

Keywords

• single-source shortest paths (SSSP)
• Bellman–Ford
• Dijkstra’s algorithm
• power efficiency
• empirical methods
• power-efficient algorithms