Запрос относительно алгоритма dijkstra

Я пытаюсь найти кратчайший путь между двумя узлами в наборе данных. я реализован алгоритм dijkstra и я использую его для доказательства учитывая два узла (например: Andrew_Card и Dick_Cheney) нет существует путь между источником и пунктом назначения. Однако я нахожу что моя программа убивается операционной системой.

После отладки я обнаружил, что проблема может быть связана с ресурсом выделение в ОЗУ. Что касается алгоритма dijkstra, если число узлов, n = 16,375,503, то требование пространства

 n*n = 16,375,503 * 16,375,503 > 10^{14}.

Для запуска этого алгоритма в памяти нам нужно как минимум

(10^{14} * 4) / (1024 * 1024 * 1024) = 10^5 GB  (approximately equal)
of RAM.

Таким образом, невозможно найти кратчайший путь, используя dijkstra, если мы намерены сохранить большой связный граф в памяти. Пожалуйста, поправьте меня, если я ошибаюсь, поскольку я застрял на этом с давних времен? Или, если может быть какая-то другая причина, которую я должен проверить, тогда, пожалуйста, укажите мне тоже.

Я реализовал программу на С++

Нет. краев = 25 908 132

Ответы

Ответ 1

Если количество ребер относительно невелико (так что все ребра могут вписываться в основную память), вы можете просто сохранить граф, используя список смежности. Для него требуется O(V + E) память вместо O(V^2). Кроме того, вы можете использовать алгоритм Дейкстры с приоритетной очередью. Он хорошо работает для разреженных графиков (он имеет O(E log V) временную сложность). Этот подход должен отлично работать для графика с 2 * 10^7 вершинами и ребрами (хорошая реализация может легко вписаться в основную память и работать не более нескольких минут).

Ответ 2

Если вам нужно просто расстояние между двумя узлами, используйте что-то вроде A*.

Но если вы делаете все кратчайшие пути, то вы определенно застряли в пространстве O(n^2). Вы находите ответы O(n^2) - так что вы не можете сделать ничего лучше, чем хранить их все.

Ответ 3

С точки зрения того, что ваша программа действительно исчерпала память, заверните свой callsite в блок try-catch и посмотрите, получаете ли вы исключение std:: bad_alloc. Пока вы не увидите исключение, которое вы ловите, не делайте предположений о том, какая часть вашей программы терпит неудачу.

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

A *: http://en.wikipedia.org/wiki/A * _search_algorithm

Иерархия сокращения: http://algo2.iti.kit.edu/schultes/hwy/contract.pdf

Ответ 4

Вы должны найти способ уменьшить количество узлов. Количество узлов велико. Вы можете использовать диаграмму Вороного для уменьшения количества узлов.

Ответ 5

В улучшении можно было бы хранить вершины в очереди приоритетов только один раз. И обновите очередь приоритетов, вместо того, чтобы снова и снова добавлять одну и ту же вершину в очередь приоритетов.