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

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