Некоторые методы оптимизации алгоритмов поиска кратчайших путей:

• Двухэтапные алгоритмы. 2 На этапе предобработки запускается единожды для графа и может занимать много времени, рассчитывает вспомогательную информацию. 2 На этапе запроса используется полученная во время предобработки информация, который должен выполняться очень быстро (в реальном времени). 2
• Алгоритм ALT. 2 На этапе предобработки берётся небольшое количество вершин (например, 16), которые обозначаются как ориентиры. 2 Для каждого из ориентиров считаются кратчайшие пути до всех вершин и сохраняются эти пути. 2 На этапе запроса используется алгоритм A*, и если некоторое ребро находится на кратчайшем пути между исходной точкой и ориентиром — по нему идут в первую очередь. 2
• Алгоритм имитации отжига (Simulated annealing). 3 Один из примеров методов Монте-Карло, основанный на физическом процессе, который происходит при кристаллизации вещества. 3 Для использования этого алгоритма необходимо определить функцию энергии (целевую функцию, которую оптимизируют), убывающую функцию изменения «температуры» и функцию, порождающую новое состояние. 3
• Метод k-кратчайших путей (k-path). 4 Позволяет находить упорядоченный список доступных альтернативных маршрутов между двумя выбранными узлами. 4