Насколько я понимаю, при динамических весах необходимо в порядке возрастания ребер перебрать все возможные пути, рассчитывая вес каждого ребра с учетом времени, потому, как более всегда малорёберный путь может оказаться длиннее по времени. Можно построить граф, взяв за вес минимальное теоретические время между остановками (у самого быстрого автобуса), а затем отфильтровать заведомо долгие маршруты. Например, был найден маршрут из 5 остановок в 3 часа, который реально (с ожиданием, пересадками и т.п.) займёт 5 часов, значит ищем дальше пока теоретические время графа не превышает 5 часов.