Floyd-Warshall trabaja en O (N ^ 3). No parece que algo similar deba pasar aquí 🙂
Comencemos con un problema mucho más simple: ¿cómo verificar si el borde dado se encuentra en la ruta más corta de A a B? Para verificar el borde C-> D, debe verificar que L (A, C) + costo (C, D) + L (D, B) = L (A, B), donde L denota la distancia más corta entre dos vértices Significa que tomará la ruta más corta de A a C, luego usará el borde C-> D, luego tomará la ruta más corta de D a B, y le dará el mismo valor que la longitud de la ruta más corta de A a B.
Bien, la siguiente pregunta: ¿cómo contar el número de formas más cortas de A a B de modo que contengan el borde C-> D? Esta parte también es fácil: debe almacenar varias formas más cortas, no solo la longitud de la ruta más corta. Ahora tiene dos posibilidades: el borde C-> D no pertenece a ninguna ruta más corta (ya sabe cómo verificarlo), o puede tomar cualquiera de las rutas A-> C más cortas, cualquiera de las D-> B más cortas caminos y fusionarlos con C-> D edge. Entonces, hay formas W (A, C) * W (D, B), donde W (A, B) denota el número de caminos más cortos.
- ¿En qué orden de dificultad consideraría publicar en CVPR, ICCV, ECCV, BMVC y NIPS?
- ¿Un compromiso de fusión realmente necesita dos padres?
- Cómo encontrar las especificaciones de una computadora
- ¿Qué hacen los desarrolladores web?
- Cómo calificar la productividad de alguien
Te da una solución O (M * N ^ 2) (para cada borde prueba todos los pares de vértices). Necesitamos uno mejor 🙂
Ahora vamos a descubrir cómo resolver un problema para el vértice de inicio fijo. Construiremos alguna solución M * log (M), que nos dará N * M * log (M) después de aplicarlo para todos los vértices iniciales posibles y agregar resultados.
Supongamos que el vértice inicial es el vértice 1. Calcularemos dos tablas DP adicionales: DP1 [i] indica el número de rutas más cortas desde el vértice 1 al vértice i, DP2 [i] indica el número de rutas más cortas desde el vértice i al resto vértices Llamaré a la ruta A-> B buena si L (1, A) + L (A, B) = L (1, B), es decir, esta ruta puede ser parte de la ruta más corta 1-> B.
DP1 se puede calcular fácilmente procesando vértices en orden de aumento de L (1, i) y considerando todos los bordes entrantes, DP2 se puede calcular de manera similar procesando vértices en orden de disminución de L (1, i) y mirando todos los bordes salientes .
Ahora, para cada borde A-> B, si puede ser parte de la ruta más corta, entonces tenemos un valor de DP1 [A] * DP2 [B] para agregar a la respuesta; una vez más, puede combinar cualquier buen prefijo con cualquier buen sufijo
Y aquí está mi código: http://pastebin.com/jF9ky8uD.
