La respuesta de Zhenrui Liao es la mejor que yo sepa.
Solo como una adición: puede resolver un problema similar utilizando el algoritmo de Floyd – Warshall o Dijkstra para obtener el camino más corto. Imagina que tienes suficientes recursos para hacer todas las conexiones posibles entre los castillos. Luego, puedes usar Floyd-Warshall para encontrar los caminos más cortos para los 28 pares posibles. Si por alguna razón no usaste una de las rutas al final del proceso, puedes deshacerte de esas rutas y terminarás con todas las rutas que necesitas para obtener todas las rutas más cortas (puedes hacer la misma repetición usando Dijkstra es varias veces para cada borde, pero creo que es un poco más costoso para gráficos no dispersos).
La solución de Zhenrui Liao le dará el árbol de expansión mínimo (gráfico sin ciclos), también conocido como “cómo construir el camino menos costoso pero eficiente”. Mi solución le dará el gráfico que contiene todos los caminos más cortos, también conocido como “cómo desperdiciar toneladas de pavimento innecesario a corto plazo, pero asegurando el tiempo de viaje más corto para todos a largo plazo”.
Esto suena como tarea, así que supongo que la solución de Zhenrui es la mejor, pero ten en cuenta que a veces te preguntan otro tipo de soluciones.
- ¿Cuál es la diferencia entre 802.11, a / b / g / ny 802.11, b / g / ny cuál es mejor?
- ¿Cómo ayuda la transformación rápida de Fourier en la multiplicación polinómica más rápida?
- Cómo resolverlo y (x) ” = h / (y (x)) ^ 2 donde h es constante
- ¿Hay alguna prueba matemática de que es imposible encontrar una ecuación (algoritmo) para generar todos los números primos?
- Cómo resolver [matemáticas] \ log \ frac {7} {4} + \ log \ frac {8} {7} [/ matemáticas]