This study revisits the Canadian Traveller Problem (CTP), which finds applications to dynamic navigation systems. Given a road network $G=(V,E)$ with a source $s$ and a destination $t$ in $V$, a traveller knows the entire network in advance, and wishes to travel as quickly as possible from $s$ to $t$, but discovers online that some roads are blocked (e.g., by snow or accidents) once reaching them. The objective is to derive an adaptive strategy so that its competitive ratio, which compares the distance traversed with that of the static shortest $s,t$-path in hindsight, is minimized. This problem was initiated by Papadimitriou and Yannakakis in 1991. They proved that it is PSPACE-complete to obtain an algorithm with a bounded competitive ratio. Furthermore, if at most $k$ roads can be blocked, then the optimal competitive ratio for a deterministic online algorithm is $2k+1$, while the only randomized result known is a lower bound of $k+1$.

In this study, we show for the first time that a polynomial time randomized algorithm can beat the best deterministic algorithms, surpassing the $2k+1$ lower bound by an $o(1)$ factor. Moreover, we prove the randomized algorithm achieving a better $(1.7k +1)$-competitive ratio in pseudo-polynomial time.

We will present a version of Bony's strong maximum principle for degenerate PDEs. We will mainly discuss the proof and its applications in studying rigidity problems in geometry.