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

In the Switching Tower of Hanoi interpretation of Sierpiński graphs  Spn, 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=3p=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 nn. Elementary algorithms for the length of the shortest path(s) and the best first move/edge are also presented.