Para la pregunta 1:
- Veamos el entorno y el costo del tiempo de ejecución de Dijkstra
- => Complejidad de tiempo = O (V + E)
- => Complejidad espacial = O (V + E)
- => Es un algoritmo de un núcleo, una máquina con un espacio de direcciones
- Veamos a los usuarios de Facebook db
- Usuarios en db> 5 mil millones (activo + inactivo)
- datos distribuidos en múltiples máquinas
- Molinos de tiempo esperado
- Como puede ver arriba, el algoritmo realmente no coincide con el contexto y los requisitos
- ¿Cómo se resuelven?
- versiones paralelas de algoritmos
- cachés medio calculados (este caché ayuda a la ejecución en tiempo de ejecución mucho más rápido para múltiples problemas en Facebook)
- técnicas de poda
- división de gráficos y aplicación individual de algos en cada parte
- algoritmos limitantes en pasos específicos (detener después de la profundidad ‘n’)
- etc …
- Como Bellman-Ford es aún más complejo que Dijkstra, el mismo problema también se aplica aquí