Алгоритм кратчайшего пути (например, Дейкстры) для 500+ путевых точек / узлов?

Question

Я спрашивал об алгоритме кратчайшего пути здесь: Двухсторонний поиск путевых точек: комбинации WP для перехода от curLocation к targetLocation

(Чтобы понять мою ситуацию, прочитайте этот вопрос, а также этот.)

Похоже, что алгоритм кратчайшего пути Дейкстры сможет сделать то, что мне нужно. Однако в моей карте маршрутов содержится от 500 до 1000 узлов.

Реализации, которые я видел до сих пор, ограничили количество узлов до 50. Мой вопрос: Должен ли я по-прежнему использовать алгоритм кратчайшего пути Дейкстры или альтернативу? Есть ли реализации в Java?

Answer 1

Вы не знаете, пока не попробуете.

1000 узлов на самом деле не так уж много.Алгоритм Дейкстры имеет линейную сложность числа ребер, а число ребер в худшем случае квадратично по числу узлов.Из вашего описания графика трудно определить, сколько существует ребер, но даже полные 1.000.000 не очень велики.

Основная проблема заключается в том, что вы реализуете это правильно, используя очередь приоритетов .

Редактировать : Рассел и Норвиг , 2-е изд., описать набор общих алгоритмов поиска в главах 3 и 4. Что ониПоиск по графу с равномерной стоимостью - это, по сути, алгоритм Дейкстры.Если вы будете следовать их инструкциям, вы можете легко расширить алгоритм поиска A *, если возникнет такая необходимость.

Answer 2

Нахождение кратчайшего пути в метрическом двухмерном мире - учебный пример алгоритма A *. Ваша эвристическая функция должна быть прямой линией от каждой путевой точки до вашей цели.

Answer 3

Алгоритм дижкестры не является простым или крускал, он вычисляет mst в целом, когда последний использует только ребро.какой другой алгоритм ты имеешь в виду?