# Canadian traveller problem

> English word · Noun

## Definitions
1. A generalization of the shortest path problem to graphs that are only partially observable (i.e. the graph is revealed while it is being explored).

## Etymology
Introduced by Christos Papadimitriou and Mihalis Yannakakis in 1989. Supposed to allude to the difficulties experienced by Canadian drivers with snowfall randomly blocking roads.

## Source
Compiled from Wiktionary via kaikki.org (CC BY-SA). Data vintage: 2026-05-06.
Canonical page: https://plainspell.com/en/word/canadian-traveller-problem