Какую самую быструю реализацию Dijkstra вы знаете (в C ++)?

Question

Я недавно приложил 3-ю версию алгоритма Дейкстры для кратчайшего пути из одного источника в мой проект.

Я понимаю, что существует множество различных реализаций, которые сильно различаются по производительности, а также по качеству результата в больших графах. С моим набором данных (> 100 000 вершин) время выполнения варьируется от 20 минут до нескольких секунд. Кратчайшие пути также варьируются на 1-2%.

Какую лучшую реализацию вы знаете?

EDIT: Мои данные - это гидравлическая сеть с 1-5 вершинами на узел. Это сопоставимо с картой улиц. Я сделал некоторые изменения в уже ускоренном алгоритме (используя отсортированный список для всех оставшихся узлов) и теперь нашел те же результаты за долю времени. Я искал такую ​​вещь довольно давно. Интересно, такая реализация уже существует.

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

РЕДАКТИРОВАТЬ 2: Я узнал, что различия в найденном пути действительно являются моей ошибкой. Я вставил специальную обработку для некоторых вершин (действует только в одном направлении) и забыл об этом в другой реализации.

НО Я все еще более чем удивлен, что Дейкстра может быть значительно ускорена следующим изменением: В общем случае алгоритм Дейкстры содержит цикл, подобный следующему:

MyListType toDoList; // List sorted by smallest distance 
InsertAllNodes(toDoList);
while(! toDoList.empty())
{
    MyNodeType *node = *toDoList.first();
    toDoList.erase(toDoList.first());
    ...
}

Если вы немного измените это, он работает так же, но работает лучше:

MyListType toDoList; // List sorted by smallest distance 
toDoList.insert(startNode);
while(! toDoList.empty())
{
    MyNodeType *node = *toDoList.first();
    toDoList.erase(toDoList.first());
    for(MyNeigborType *x = node.Neigbors; x != NULL; x++)
    {
        ...
        toDoList.insert(x->Node);
    }
}

Кажется, что эта модификация сокращает время выполнения на порядок не величины, а порядка экспоненты. Это уменьшило мою рабочую форму с 30 секунд до менее 2. Я не могу найти эту модификацию ни в одной литературе. Также очень ясно, что причина кроется в отсортированном списке. Вставка / стирание работает намного хуже с 100.000 элементов, которые заполнены рукой.

ОТВЕТ:

После долгих поисков я нашел это сам. Ответ очевиден: увеличить граф lib . Удивительно - я не нашел это в течение долгого времени. Если вы думаете, что между реализациями Dijkstra нет различий в производительности, см. wikipedia .

Answer 1

Лучшие реализации, известные для дорожных сетей (> 1 миллиона узлов), имеют время запроса, выраженное в микро секундах Для получения более подробной информации смотрите 9-й этап внедрения DIMACS (2006). Обратите внимание, что это не просто Дейкстра, конечно, потому что весь смысл заключался в том, чтобы получить результаты быстрее.

Answer 2

Может быть, я не отвечаю на ваш вопрос. Моя точка зрения - зачем использовать Dijkstra, когда для вашей задачи есть более эффективные алгоритмы. Если ваш граф заполняет треугольное свойство (это евклидов граф)

| абы | + | Ьс | > | ac |

(расстояние от узла a до узла b плюс расстояние от узла b до узла c больше, чем расстояние от узла a до узла c), тогда вы можете применить алгоритм A *. Этот алгоритм довольно эффективен. В противном случае рассмотрите возможность использования эвристики. Реализация не является главной проблемой. Используемый алгоритм имеет значение.

Answer 3

Два замечания, которые я хотел бы сделать: 1) Дейкстра против А * Алгоритм Дейкстры - это алгоритм динамического программирования, а не эвристический. A * - это эвристика, поскольку она также использует эвристическую функцию (скажем, h (x)), чтобы «оценить», насколько близко точка x достигает конечной точки. Эта информация используется в последующих решениях о том, какие узлы следует исследовать следующим.

Для таких случаев, как евклидов граф, A * работает хорошо, потому что эвристическую функцию легко определить (например, можно просто использовать евклидово расстояние). Однако для неевклидовых графов может быть сложнее определить эвристическую функцию, и неправильное определение может привести к неоптимальному пути.

Следовательно, dijkstra имеет преимущество перед A *, заключающееся в том, что он работает для любого общего графа (за исключением того, что A * в некоторых случаях быстрее). Вполне возможно, что некоторые реализации используют эти алгоритмы взаимозаменяемо, что приводит к разным результатам.

2) Алгоритм Дейкстры (и другие, такие как A *) используют очередь приоритетов для получения следующего узла для исследования. Хорошая реализация может использовать кучу вместо очереди, а еще лучше - кучу Фибоначчи. Это может объяснить разные времена выполнения.

Answer 4

В последний раз, когда я проверял, алгоритм Дейкстры возвращает оптимальное решение. Все «истинные» реализации Дейкстры должны возвращать один и тот же результат каждый раз.

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

Answer 5

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

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

Проблема в том, что не существует "одной самой быстрой" версии алгоритма.