Задача кратчайшего пути дийсктра с дуговыми флажками

Question

На больших графиках, таких как дорожная сеть с узлом 2M, dijkstra не может решить проблему кратчайшего пути в подходящее время. Нам нужно сократить время выполнения запроса пути менее чем за 1 секунду, и я реализую способ указания флага дуги, чтобы ускорить работу dijkstra. Кто-нибудь знает о том, как реализовать предварительную обработку флагов дуги и запрос. Предобработка флагов дуги имеет другой алгоритм, который мне нужен, быстрый.

Answer 1

Вы пробовали A *?Это уточнение алгоритма Дейкстры, которое обычно работает лучше;кроме того, вы можете настроить его так, чтобы он предпочитал скорость поиска оптимальности, если это возможно.