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

До сих пор неизвестно, можно ли найти более эффективные множества транзитных узлов или лучший фильтр локальности для дальнейшейго улучшения производительности. Неясно также, может ли маршрутизация при помощи транзитных узлов успешно применяться к другим типам графов, отличным от дорожных сетей. В этом контексте было бы желательно получить какие-либо теоретические гарантии, применимые к любому графу, обладающему определенными свойствами. Для некоторых практических областей применения пригодилась бы ''динамическая'' версия маршрутизации при помощи транзитных узлов для работы с сетями, зависящими от времени, или непредсказуемыми изменениями весов дуг, вызванными, к примеру, заторами на дорогах. Последний сценарий может обрабатываться с помощью родственного подхода из работы [8], однако он работает гораздо медленнее, чем маршрутизация при помощи транзитных узлов.