Otra versión del problema de la ruta más corta es encontrar las rutas más cortas del origen a todos los demás nodos de la red. Nótese que el algoritmo obtiene las rutas más cortas a cada nodo que está más cerca del origen que el destino. Entonces, si todos los nodos son destinos potenciales, la única modificación que se necesita es que el algoritmo no se detenga, hasta que todos los nodos se hayan resuelto.
Otra versión aún más general del problema de la ruta más corta es encontrar la ruta más corta desde todos los nodos a todos los demás nodos. Otra opción es eliminar la restricción de que las "distancias" (valores de los arcos) sean no negativas. Se pueden poner también restricciones sobre las trayectorias que se pueden seguir. Todas estas variaciones surgen en ocasiones en la práctica y por esto han sido estudiadas por los investigadores.
Los algoritmos para una gran variadad de problemas de optimizanción de análisis combinatorio - como los problemas de diseño de ruta de vehículos- con frecuencia utlizan como parte de sus subrutinas, la solución de un gran número de problemas de la ruta más corta. Aunque no se dispone de espacio suficiente para profundizar en este tema, tal vez esta aplicación sea una de las más importantes de este algoritmo.
No hay comentarios.:
Publicar un comentario