El problema de los caminos más cortos encuentra aplicaciones en múltiples campos. De particular interés en el campo del transporte es la variante de encontrar caminos más cortos simples (KSSP), que tiene una complejidad mayor. Esta investigación presenta un algoritmo novedoso de etiquetado para el problema KSSP de múltiples destinos en redes dirigidas que evita aplicaciones repetidas del algoritmo a cada destino (necesario en los algoritmos existentes basados en desviaciones), lo que resulta en una aceleración significativa de la computación. Se muestra que el algoritmo propuesto es exacto y lo suficientemente flexible para manejar varias variantes del problema modificando adecuadamente la condición de terminación. Teóricamente, también se demuestra que es más rápido que los algoritmos de vanguardia en redes dispersas y densas siempre que el número de etiquetas creadas sea sub-polynomial en el tamaño de la red. Se proponen un método heurístico y estructuras de datos optimizadas para mejorar la escalabilidad del algoritmo y su rendimiento en el peor de los casos. Los resultados computacionales muestran que la heurística propuesta proporciona aceleraciones de tiempo computacional de dos a tres órdenes de magnitud (29-1416 veces en diferentes redes) con una pérdida insignificante en la calidad de la solución (desviación promedio máxima del 0.167% de la solución óptima). Finalmente, se ilustra una aplicación práctica del método propuesto para determinar la gravedad de un borde (importancia estructural relativa) en una red.