Optimal routing in double loop networks

In this paper, we study the problem of finding the shortest path in circulant graphs with an arbitrary number of jumps. We provide algorithms specifically tailored for weighted undirected and directed circulant graphs with two jumps which compute the shortest path. Our method only requires O(logN) arithmetic operations and the total bit complexity is O(log2NloglogNlogloglogN), where N is the number of the graph’s vertices. This elementary and efficient shortest path algorithm has been derived from the Closest Vector Problem (CVP) of lattices in dimension two and with an ℓ1 norm.