Puede hacerlo utilizando el algoritmo de Dijkstra dos veces. Aquí es cómo:
Primero, ejecute el algoritmo de Dikstra una vez para obtener la distancia más corta entre la fuente ‘ s’ y el destino ‘ t’. Ahora, lo que esencialmente debe hacer es eliminar esta ruta del gráfico. Lo importante a tener en cuenta aquí es que puede haber más de una ruta que tenga el peso / longitud igual a la distancia más corta. Debe eliminar todos los bordes que se encuentran en cualquiera de los caminos más cortos de ‘s’ a ‘t’.
Para hacer esto, procesa todos los bordes uno por uno. Para cualquier borde (u, v), si dist [u] == dist [v] – w (u, v), elimine este borde. Donde, la matriz dist [] es la matriz de distancia que creó durante la primera Dijkstra.
Ahora que ha eliminado todos los bordes que se encuentran en el camino más corto, puede ejecutar el segundo Dijkstra y obtener el segundo camino más pequeño.
- Además del algoritmo de tallado de costura, ¿qué otros algoritmos se pueden usar para Image Resizer?
- Si estudié modelado matemático financiero avanzado en la universidad con un coeficiente intelectual de 145, ¿con qué probabilidad podría construir un algoritmo HFT rentable?
- ¿Cuál es la habilidad más importante para desarrollar en algoritmos?
- ¿Cuál es el inverso matemático de 2 ^ N?
- ¿Qué tan preciso es el algoritmo de predicción de personalidad de Faception?
Aquí hay una pregunta similar de SPOJ: SPOJ.com – Problema SAMER08A