Actualizando dinámicamente las rutas más cortas

Question

Tengo un gráfico en el que con frecuencia necesito conocer todas las rutas más cortas (o más bien sus longitudes). Como no quiero recalcularlos, los almaceno en una matriz simple y simplemente los recupero de allí. Sin embargo, dado que el gráfico también podría cambiar con el tiempo, tendré que volver a calcularlos en determinados momentos.

Por ahora los siguientes cambios puede ocurrir:

• Adición de un nodo y un borde a la misma a la gráfica

• Cambio de la longitud de un borde

• Adición de un nuevo borde del gráfico

• Eliminación de un borde o eliminación de un nodo

En todos los casos, todos los nodos siempre estarán conectados y todos los bordes tendrán pesos positivos. Además, el gráfico no está dirigido. La secuencia de operaciones es tal, que todos los nodos siempre serán del mismo componente del gráfico. Si se elimina un nodo o borde antes de que se hayan agregado estos otros nodos y bordes para que el gráfico nunca se separe.

Por ahora estoy planeando simplemente hacer las actualizaciones y luego propagar todos los cambios a través de la estructura del gráfico. Sin embargo, todavía no estoy seguro de cómo manejar esto correctamente. ¿Cómo tratar de lograr estas actualizaciones de la longitud en caché?

EDITAR:

Como algunos de ustedes han señalado que podría ser necesario recurrir a recalcular todo cuando se añade un nodo o se cambia un enlace. Esto podría ser, por ejemplo, cuando todas las distancias cambian a través de la actualización. Sin embargo, si solo propago los cambios a través del gráfico y hago una relajación similar a la forma en que se hacen los dijkstras, podría tener que relajar el mismo nodo varias veces, porque es posible que no elija el orden óptimo. La pregunta sería cómo ordenar los pasos de relajación, así que evito tantas actualizaciones como sea posible.

No estoy seguro de que esto tenga mucho sentido sin la idea real que tengo en mente, pero espero que esto aclare un poco más.

Answer 1

El D* family of search algorithms se refieren exactamente a la actualización de las rutas de cortocircuito en los gráficos dinámicamente cambiantes. Los algoritmos fueron desarrollados para problemas de planificación de ruta de robot móvil. Aunque los algoritmos solo devuelven la ruta más corta desde el objetivo hasta la ubicación actual del robot, es posible que también pueda usar sus reglas de contabilidad y actualización para los problemas de rutas más cortas.

Answer 2

Puede manejar el caso en el que está eliminando un borde/nodo con bastante facilidad. Simplemente haga un seguimiento de la ruta real entre los nodos. Luego, cuando se elimina un borde/nodo, revise sus rutas y vea cuáles se ven afectados por el cambio. Recalcule los caminos más cortos para estos.

En el caso donde aumente el peso de un borde, puede usar la misma técnica.

Los otros casos son significativamente más difíciles de tratar. No conozco ningún algoritmo/estructura de datos que acelere el recálculo.