Shortest-Path Indices: Establishing a Methodology for Shortest-Path Problems

During the last years, impressive progress has been achieved in
the field of algorithm engineering. A problem becoming more and
more important is that of data dependency: the performance of an
algorithm often highly depends on the input. Yet, for a given
input, it is highly non-trivial to select the best solving strategy.

In this work, we introduce a new methodology for evaluating
speed-up techniques for DijkstraŽs Algorithm: we examine the
shortest-path structure of networks using simple indices in
order to predict how well speed-up techniques perform on
specific networks. More precisely, we introduce the ReCo-Index
that indicates the strength of hierarchy of the input. In
addition, we present a second index, called shortest-path
entropy, taking into account the mutual importance of
consecutive edges. As a third index, the update impact measures
the change of the shortest-paths structure in a network whenever
it is altered. For each index, we present an algorithm for
computing it efficiently. An experimental evaluation confirms
the correlation of indices and speed-up techniques.