Недавно я приложил к моему проекту 3-ю версию алгоритма Дейкстры для кратчайшего пути одного источника.
Я понимаю, что существует множество различных реализаций, которые сильно различаются по производительности, а также отличаются качеством результата на больших графиках. С моим набором данных ( > 100.000 вершин) время выполнения варьируется от 20 минут до нескольких секунд. Самые короткие пути также изменяются на 1-2%.
Какая наилучшая реализация вы знаете?
EDIT: Мои данные - это гидравлическая сеть с 1 - 5 вершинами на node. Это сопоставимо с уличной картой. Я внесла некоторые изменения в уже ускоренный алгоритм (используя отсортированный список для всех остальных узлов) и теперь обнаружил те же результаты за долю времени. Некоторое время я искал такое. Интересно, существует ли такая реализация.
Я не могу объяснить небольшие различия в результатах. Я знаю, что Дейкстра не эвристичен, но все реализации кажутся правильными. Более быстрые решения имеют результаты с более короткими путями. Я использую только математику с двойной точностью.
ИЗМЕНИТЬ 2: Я узнал, что различия в найденном пути действительно являются моей ошибкой. Я вставил специальную обработку для некоторых вершин (только в одном направлении) и забыл об этом в другой реализации.
НО im все же более чем удивлен тем, что Dijkstra можно резко ускорить следующим изменением: В общем случае алгоритм Дейкстры содержит петлю типа:
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.
