Концептуально, вы берете тот же базовый алгоритм для оценки расстояния между A и B, но вместо расстояния вы должны оценивать время. Дейкстра может сделать и то, и другое, если вы дадите ей правильные данные.
Вы привыкли видеть карту как меру расстояния. Тем не менее, та же карта может быть мерой времени; все, что вам нужно, это добавить данные о средней скорости, и время, которое потребуется, чтобы преодолеть определенное расстояние конкретной дороги, потрясет себя. Вы даже можете визуализировать карту с точки зрения времени; маршруты, которые занимают больше времени, будут дольше. Дейкстре все равно, что он оценивает; он просто заботится о том, чтобы найти непрерывный маршрут с наименьшим числом, и то, представляет ли это число длину или время, не имеет значения.
Чтобы включить скорость, наивные алгоритмы просто используют дневное ограничение скорости и предполагают, что вам никогда не придется останавливаться при переходе от А к В; более продвинутые алгоритмы могут включать информацию о времени суток и схемах движения (которые будут влиять на среднюю скорость движения по этой дороге в это время), а также о том, является ли дорога автострадой или наземной улицей (и, таким образом, дают обоснованные предположения о том, сколько времени прошло) на перекрестке). То, что вы используете, зависит от того, что у вас есть, но базовое четырех- или пятислойное измерение времени суток должно быть подходящим для всех приложений, кроме абсолютных, наиболее критичных ко времени. Для каждого направления каждой дороги на вашей карте вам нужна средняя скорость во время утренней лихорадки, дневной, вечерней лихорадки и ночи, возможно, с учетом чисел в обеденное время. Как только вы это сделаете, это сравнительно простое изменение алгоритма Дейкстры, которое передается во время дня и позволяет ему оценивать маршруты на основе времени.