Problema de la amplitud

En algoritmos gráficos, el problema de la amplitud es el problema de encontrar un camino entre dos vértices designados en un gráfico ponderado, maximizando el peso del borde de menor peso en la ruta. El problema del camino más ancho también se conoce como el cuello de botella, el problema del camino más corto o más bien, el máximo problema de este camino es la capacidad. Es posible adaptar la mayoría de los algoritmos del camino más corto para calcular trayectorias muy amplias mediante la modificación de las mismas para utilizar la distancia del cuello de botella en lugar de la longitud de la trayectoria.​ Sin embargo, en muchos casos incluso los algoritmos más rápidos son posibles. Por ejemplo, en un gráfico que represente las conexiones entre los routers de la Internet, el peso de una arista representa el ancho de banda de una conexión entre dos routers, el problema del camino más ancho es el problema de encontrar una ruta de extremo a extremo entre dos nodos que tengan el máximo ancho de banda posible.​ El peso más pequeño de la arista en este camino se conoce como la capacidad o ancho de banda de la ruta. Así como sus aplicaciones en el enrutamiento de red, el problema del camino más ancho es también un componente importante del método de Schulze para decidir el ganador de una elección de múltiples vías,​ y se ha aplicado a la composición digital​ vía análisis metabólico​ y cálculo de flujos máximos.​ Un problema relacionado, es el problema del camino minimax, el cual supone por el camino que minimiza el peso máximo de cualquiera de sus aristas. Tiene aplicaciones que incluyen la planificación del transporte.​ Cualquier algoritmo para el problema del camino más amplio puede ser transformado en un algoritmo para el problema del camino minimax, o viceversa, mediante la inversión del sentido de todas las comparaciones de peso realizadas por el algoritmo, o de manera equivalente mediante la sustitución de todo peso.