Canadian traveller problem

noun

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).

Ask AI about this wordChatGPTClaudePerplexityGoogle AIGrok

Meanings

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

Origin

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

Full word history & related roots →
Cite this entry
APA

Canadian traveller problem. (n.d.). In WatkinsX Dictionary. Retrieved November 4, 2026, from https://dictionary.watkinsx.com/word/Canadian%20traveller%20problem

MLA

“Canadian traveller problem.” WatkinsX Dictionary, https://dictionary.watkinsx.com/word/Canadian%20traveller%20problem. Accessed November 4, 2026.

Chicago

WatkinsX Dictionary, s.v. “Canadian traveller problem,” accessed November 4, 2026, https://dictionary.watkinsx.com/word/Canadian%20traveller%20problem.

Source: Canadian traveller problem on Wiktionary, CC BY-SA 4.0.