# An optimal randomized online algorithm for the k-Canadian Traveller Problem on node-disjoint paths

We consider the $k$ ‐Canadian Traveller Problem, which asks for a shortest path between two nodes $s$ and $t$ in an undirected graph, where up to $k$ edges may be blocked. An online algorithm learns about a blocked edge when reaching one of its endpoints. Recently, it has been shown that no randomized online algorithm can be better than $\left(k+1\right)$ ‐competitive, even if all $s$ $t$ ‐paths are node‐disjoint. We show that the bound is tight by constructing a randomized online algorithm for this case that achieves the ratio against an oblivious adversary and is therefore best possible.