Маршрутизация в дорожных сетях с транзитными узлами: различия между версиями

Пусть дан ориентированный граф G = (V, E) с неотрицательными весами ребер. Необходимо вычислит кратчайший путь по графу G из вершины-источника s в целевую вершину t для заданных s и t. Предполагая, что граф G остается неизменными и что будет много запросов с указанием источника и цели, имеет смысл потратить некоторое время на этап предварительной обработки, который позволит очень быстро отвечать на запросы. На выходе, в зависимости от приложения, ожидается либо полное описание кратчайшего пути, либо только его длина d(s, t).

Классический алгоритм Дейкстры для решения этой задачи [ ] итеративно посещает все вершины по порядку расстояния от источника до тех пор, пока не будет достигнута целевая вершина. При обработке очень больших графов алгоритм начинает работать слишком медленно для многих приложений, из-за чего возникает необходимость в применении более специфичных техник, использующих особые свойства конкретного графа. Крайне важным на практике случаем является маршрутизация в дорожных сетях, в которых слияния и пересечения дорог трактуются как узлы, а участки дорог – как ребра, вес которых определяется некоторой весовой функцией, например, от ожидаемого времени в пути, расстояни и потребления топлива. Дорожные сети обычно являются разреженными (т. е. |E| = O(|V|)), почти планарными (т. е. в них очень небольшое число переездов) и иерархическими (т. е. можно выделить более или менее «важные» дороги). Обзор различных технологий ускорения для этой конкретной задачи приведен в работе [7].