Существует ли какой-либо алгоритм кратчайшего и безопасного пути, принимающий общее количество аварий в качестве параметра лучше, чем алгоритм Дейкстры?

Question

Этот вопрос для моего последнего года проекта.Этот проект полностью посвящен рекомендации безопасного маршрута для пользователя, чтобы избежать подверженных авариям улиц.Для этой цели мы ищем алгоритм, который имеет лучшую временную сложность и пространственную сложность, чем Dijsta.

Answer 1

Предполагая, что вы можете сформулировать эту проблему следующим образом:

• найти путь
• в ориентированном графе
• с неотрицательными весами

Вы можете решить это с Thorup [2004]
Этот конкретный алгоритм претендует на выполнение в O (E + V * log log V)

Пример реализации можно найти здесь