Recientemente adjunté la 3ra versión del algoritmo de Dijkstra para la ruta más corta de una sola fuente en mi proyecto.¿Cuál es la implementación más rápida de Dijkstra que conoces (en C++)?
Me doy cuenta de que hay muchas implementaciones diferentes que varían mucho en rendimiento y también varían en la calidad del resultado en gráficos grandes. Con mi conjunto de datos (> 100.000 vértices) el tiempo de ejecución varía de 20 minutos a unos pocos segundos. Los caminos más cortos también varían en un 1-2%.
¿Cuál es la mejor implementación que conoces?
EDIT: My Data es una red hidráulica, con 1 a 5 vértices por nodo. Es comparable a un mapa de calles. Hice algunas modificaciones a un algoritmo ya acelerado (utilizando una lista ordenada para todos los nodos restantes) y ahora encuentro los mismos resultados en una fracción de tiempo. He buscado tal cosa bastante tiempo. Me pregunto si tal implementación ya existe.
No puedo explicar las pequeñas diferencias en los resultados. Sé que Dijkstra no es heurístico, pero todas las implementaciones parecen ser correctas. Las soluciones más rápidas tienen los resultados con trayectorias más cortas. Utilizo matemática de precisión doble exclusivamente.
EDIT 2: Descubrí que las diferencias en la ruta encontrada son de hecho mi culpa. Inserté un manejo especial para algunos vértices (solo válido en una dirección) y me olvidé de eso en la otra implementación.
PERO mejorar aún más sorprendido de que Dijkstra se puede acelerar de manera espectacular por el siguiente cambio: En general un algoritmo de Dijkstra contiene un bucle como:
MyListType toDoList; // List sorted by smallest distance
InsertAllNodes(toDoList);
while(! toDoList.empty())
{
MyNodeType *node = *toDoList.first();
toDoList.erase(toDoList.first());
...
}
Si cambia esto un poco, se funciona de la misma, pero tiene un mejor rendimiento:
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);
}
}
parece que esta modificación reduce el tiempo de ejecución de una orden de magnitud no, pero una orden de exponente. Reduje mi tiempo de ejecución de 30 Segundos a menos de 2. No puedo encontrar esta modificación en ninguna literatura. También está muy claro que la razón radica en la lista ordenada. insertar/borrar se comporta mucho peor con 100.000 elementos que con una mano llena de.
RESPUESTA:
Después de mucho googlear lo encontré a mí mismo. La respuesta es clara: boost graph lib. Increíble, no había encontrado esto por bastante tiempo. Si cree que no existe una variación en el rendimiento entre las implementaciones de Dijkstra, consulte wikipedia.
Un amigo mío puede implementar Dijkstra en C++ en aproximadamente 3 minutos. No he oído hablar de implementaciones más rápidas. – jbasko
Sugeriría que tal vez quiera verificar esas implementaciones ... si son correctas, todas deberían devolver el mismo camino más corto ... El algoritmo de Dijkstra no es heurístico ... – jerryjvl
Las diferencias en las rutas más cortas pueden ser el resultado de usando matemática de precisión doble, debido a errores de redondeo al sumar largas secuencias de dobles. Un orden diferente de suma puede producir diferentes errores. ¿Puedes probar tus implementaciones en enteros? –