Классический алгоритм Дейкстры идеально строит кратчайший путь, когда время проезда по каждой улице является абсолютно детерминированной константой. Но если мы проектируем навигатор для утреннего часа пик в мегаполисе или маршрутизируем пакеты в нестабильной беспроводной сети (Ad-hoc), время прохождения каждого ребра графа становится стохастической (случайной) величиной. Если просто заменить все случайные времена их средними математическими ожиданиями и запустить Дейкстру, полученный путь может оказаться катастрофически ненадежным (например, иметь огромную дисперсию задержек из-за вероятности аварий). Для решения этой проблемы исследование операций применяет аппарат Стохастических задач о кратчайшем пути (Stochastic Shortest Path, SSP).