El algoritmo es idéntico al algoritmo Ford – Fulkerson, excepto que se define el orden de búsqueda al encontrar la ruta de aumento. La ruta encontrada debe ser la ruta más corta que tenga capacidad disponible. Esto se puede encontrar mediante una búsqueda de amplitud, ya que dejamos que los bordes tengan unidades de longitud. El tiempo de ejecución de O ( V E ^ 2) se encuentra al mostrar que cada ruta de aumento se puede encontrar en el tiempo O ( E ), que cada vez que al menos uno de los bordes E se satura (un borde que tiene el flujo máximo posible ), que la distancia desde el borde saturado a la fuente a lo largo de la ruta de aumento debe ser mayor que la última vez que estuvo saturada, y que la longitud es como máximo V. Otra propiedad de este algoritmo es que la longitud de la ruta de aumento más corta aumenta monotónicamente.
Referencia: algoritmo Edmonds – Karp | Wikiwand
- ¿Cómo es que la mayoría de las empresas solicitan específicamente estructuras de datos y algoritmos? ¿Qué sucede cuando un adicto a los algoritmos con solo conocimiento de C ++ o Java es aceptado en una empresa que utiliza tecnologías web, aprende el marco utilizado desde cero?
- ¿Cuáles son algunas diferencias entre los campos de la investigación algorítmica y la investigación de operaciones?
- ¿Por qué debería vivir si mis problemas nunca se resuelven?
- ¿Cuántas matemáticas necesito para aprender sobre estructuras de datos y algoritmos?
- Cómo encontrar un árbol de expansión T con el mínimo peso máximo de trayectoria para 2 vértices en G
