We consider the ‐Canadian Traveller Problem, which asks for a shortest path between two nodes and in an undirected graph, where up to 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 ‐competitive, even if all ‐ ‐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.
