An efficient algorithm to determine all shortest paths in Sierpiński graphs

In the Switching Tower of Hanoi interpretation of Sierpinski graphs S p n , the P2 decision problem is to find out whether the largest moving disc has to be transferred once or twice in a shortest path between two given states/vertices. We construct an essentially optimal algorithm thus extending Romik’s approach for p = 3 to the general case. The algorithm makes use of three automata and the underlying theory includes a simple argument for the fact that there are at most two shortest paths between any two vertices. The total number of pairs leading to non-unique solutions is determined and employing a Markov chain argument it is shown that the number of input pairs needed for the decision is bounded above by a number independent of n . Elementary algorithms for the length of the shortest path(s) and the best first move/edge are also presented.